线性dp求解 最长子序列 —— 小题三则

---

一、最长连续等差数列

题意
给定一个包含 $N$ 个非负整数的数组，其中的第 $i$ 个整数为 $A_i$。
求最长连续等差数列长度。
$1\le T\le 100,1\le A_i\le 10^9$

思路1：dp，O(n)

既然是连续的，那只能从前一个位置转移，判断当前值 a[i] 和上一位置 a[i-1] 的差值是否能和上上位置 a[i-2] 构成等差数列。如果能，就从上一位置的状态转移。
状态定义：f[i] 表示以 i 位置结尾的最长连续等差数列长度。
状态转移：

if(a[i] - a[i-1] == a[i-1] - a[j-2]) f[i] = f[i-1] + 1;
else f[i] = 1;
1
2

Code：

#include<bits/stdc++.h>
using namespace std;

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], f[N];

signed main(){
	scanf("%d", &T);
	for(int cs = 1; cs <= T; cs ++)
	{
		scanf("%d", &n);
		for(int i=1;i<=n;i++) scanf("%d", &a[i]), f[i] = 1;
		
		int ans = 1;
		f[1] = 0;
		for(int i=2;i<=n;i++)
		{
			if(a[i]-a[i-1] == a[i-1]-a[i-2]) f[i] = f[i-1]+1;
			ans = max(ans, f[i]);
		}
		
		if(n == 1) ans = 0;
		printf("Case #%d: %d\n", cs, ans+1);
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

思路2：差分，O(n)

等差数列性质，差值为定值，也就是说等差数列的差分数组中的所有值都相同。
所以维护差分求最长相同子串就行了。
Code：

#include<bits/stdc++.h>
using namespace std;

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], f[N];

signed main(){
	scanf("%d", &T);
	for(int cs = 1; cs <= T; cs ++)
	{
		scanf("%d", &n);
		for(int i=1;i<=n;i++) scanf("%d", &a[i]);
		
		for(int i=1;i<=n;i++) f[i] = a[i] - a[i-1];
		
		f[0] = 1e9+1; //特判第0个位置，将后面的+1用于所有情况。防止出现1 2这样的情况。 
		
		int ans = 0;
		for(int i=1;i<=n;i++)
		{
			int j = i+1;
			while(f[j] == f[i] && j<=n) j++;
			ans = max(ans, j-i);
			i = j-1;
		}
		
		if(n == 1) ans = 0;
		printf("Case #%d: %d\n", cs, ans+1);
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

二、最长等差子序列

题意
给定一个包含 $N$ 个非负整数的数组，其中的第 $i$ 个整数为 $A_i$。
求最长等差子序列的长度。（子序列在原数组中不一定连续）
$1\le T\le 100,1\le A_i\le 10^9$

思路1：dp，O(nm)，m 为 Ai 最大值

状态定义：
定义 f[i, j, k] 表示，以值 i 作为等差数列末位置，差值绝对值为 j，差值正负为 k 时，最长等差子序列长度。(k ∈ {0, 1})
状态转移：
用前面位置所更新的 f[] 来更新当前位置。

f[nums[i]][j][0] = f[nums[i]+j][j][0] + 1;
if(nums[i]>=j) f[nums[i]][j][1] = f[nums[i]-j][j][1] + 1;
else f[nums[i]][j][1] = 1;
1
2
3

Code：

class Solution {
/*
 需要特别注意的是，如果a[i]+j没有出现过，那么其可以用f[a[i]+j][j]来更新为1；但是如果a[i]-j没有出现过，并且为负数的话，这个f[a[i]-j]就不会更新为1，仍然为0，就会出现错误。所以这种情况要特判为1。
 另外也不能用max(0, a[i]-j)来更新，因为在这道题中f[0]是有值的，不是始终为0。
*/
public:
    int longestArithSeqLength(vector<int>& nums) {
        int f[1010][510][2]{};
        int ans = 0;

        for(int i=0;i<nums.size();i++)
        {
            for(int j=0;j<=500;j++)
            {
                f[nums[i]][j][0] = f[nums[i]+j][j][0] + 1;
                if(nums[i]>=j) f[nums[i]][j][1] = f[nums[i]-j][j][1] + 1;
                else f[nums[i]][j][1] = 1;

                ans = max(ans, f[nums[i]][j][0]); ans = max(ans, f[nums[i]][j][1]);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路2：dp，O(n^2)

一种等差数列至少需要两个相邻位置来确定，所以可以定义两维状态来表示以这两个位置为末位置的等差数列最长长度。
状态定义：
定义 f[i, j] 表示，以 i, j 这两个位置作为末位置的等差序列的最长长度。

状态转移：f[i][j] = f[mp[2*a[i]-a[j]]][i] + 1，mp[x] 用以得到值 x 在前面出现的位置。
更新时，对于当前位置 i，遍历其后面所有位置 j，通过这两个值算出最前面的位置 k。用前面的 f[k, i] 来更新后面的 f[i, j]。

这里还用到一个技巧，由当前值和后面枚举的值可以算出等差数列前面一个位置的值，但是如何找到该值在数组中的位置呢？
可以直接用 map 标记，标记该值最后一次出现的位置。
（最后一次，那前面位置不能更新么？也是可以的，只是后面位置所能更新的长度一定不会小于前面位置所能更新长度，所以直接用最后一次出现位置来更新即可）
把当前位置 i 遍历之后，再把 a[i] 出现的位置标记为 i，这样便能保证 mp[x] 出现的位置一定在当前位置之前，用前面的答案来更新后面。

Code：

class Solution {
public:
    int longestArithSeqLength(vector<int>& a) {
        unordered_map<int,int> mp;
        int f[1010][1010]{};

        int ans = 0;
        for(int i=0;i<a.size();i++){
            for(int j=i+1;j<a.size();j++)
            {
                if(!mp.count(2*a[i]-a[j])) continue;
                f[i][j] = f[mp[2*a[i]-a[j]]][i] + 1;
                ans = max(ans, f[i][j]);
            }
            mp[a[i]] = i;
        }
        return ans + 2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

三、最长斐波那契子序列

题意
给定一个包含 $N$ 个正整数的严格递增数组，其中的第 $i$ 个整数为 $A_i$。
求最长斐波那契子序列的长度。（子序列在原数组中不一定连续）

如果序列 $X_1,X_2,...,X_n$ 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 $X_i+X_{i+1}=X_{i+2}$

思路1：set暴力，O($n^{2}logm$)，m为 Ai 最大值

将整个数组存到 set 里，二重循环遍历数列前两个位置，对于每两个初始位置，得出接下来一个数的位置。set判断其是否存在，存在的话长度++，位置更新，不断往后走。
因为是严格递增的，并且数列以斐波那契式增长，最长有43项，所以整体复杂度为O($n^{2}logm$)。
（正因为是单调递增的，非常巧妙的用set来搞）

Code

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& v) {
        set<int> st(v.begin(), v.end());
        
        int ans = 0;
        for(int i=0;i<v.size();i++)
            for(int j=i+1;j<v.size();j++)
            {
                int x = v[i], y = v[j];
                int len = 2;
                while(st.find(x+y) != st.end())
                {
                    int z = x + y;
                    x = y;
                    y = z;
                    len ++;
                }
                ans = max(ans, len);
            }
        return ans > 2 ? ans : 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路2：dp，O(n^2)

思路和上一题的第二种解法相同。
状态定义：
定义 f[i, j] 表示，以 i, j 位置作为末位置的斐波那契子序列的最长长度。
状态转移：
f[i][j] = f[mp[2*a[i]-a[j]]][i] + 1，其中 mp[x] 表示值 x 在当前位置 i 前面出现的位置。
对于当前位置 i 作为数列第2项，遍历后面的所有位置 j 作为数列第3项，通过这两个位置的值计算出第1项的值，mp[x] 得到其位置 k。
由位置 k 和 i 确定的数列来更新由位置 i 和 j 确定的数列。
同样，为了保证 mp[x] 是在当前位置 i 之前的，在遍历过当前位置之后再将 i 位置加到 map 中。
Code

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& a) {
        unordered_map<int, int> mp;
        int f[1010][1010]{};

        int ans = 0;
        for(int i=0;i<a.size();i++){
            for(int j=i+1;j<a.size();j++)
            {
                if(!mp.count(a[j]-a[i])) continue;
                f[i][j] = max(f[i][j], f[mp[a[j]-a[i]]][i] + 1);
                ans = max(ans, f[i][j]);
            }
            mp[a[i]] = i;
        }

        ans += 2;

        return ans > 2 ? ans : 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

由此可以看出，思路2对于求解这样的子序列问题具有普适性，应该熟练记忆。