Solving the longest subsequence with linear DP -- three questions

---

One 、 Longest continuous arithmetic sequence

The question
Given an inclusion $N$ An array of nonnegative integers , The first of these $i$ An integer is $A_i$.
Find the length of the longest continuous arithmetic sequence .
$1\le T\le 100,1\le A_i\le 10^9$

Ideas 1：dp,O(n)

Since it is continuous , That can only be transferred from the previous position , Judge the current value a[i] And previous position a[i-1] Whether the difference can be compared with the upper position a[i-2] Form the arithmetic sequence . If you can , Just transfer from the state of the previous position .
State definition ：f[i] Said to i The length of the longest continuous arithmetic sequence at the end of the position .
State shift ：

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

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;
}

Ideas 2： Difference ,O(n)

Properties of arithmetic sequence , The difference is the fixed value , That is to say, all values in the difference array of the arithmetic sequence are the same .
So maintain the difference to find the longest substring with the same length .
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; // Special judge 0 A place , Put the back of +1 For all situations . Prevent emergence 1 2 In this case . 
		
		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;
}

---

Two 、 Longest isochronous subsequence

The question
Given an inclusion $N$ An array of nonnegative integers , The first of these $i$ An integer is $A_i$.
Find the length of the longest arithmetic sequence .（ Subsequences are not necessarily continuous in the original array ）
$1\le T\le 100,1\le A_i\le 10^9$

Ideas 1：dp,O(nm),m by Ai Maximum

State definition ：
Definition f[i, j, k] Express , To value i As the last position of the arithmetic sequence , The absolute value of the difference is j, The difference is positive or negative k when , The length of the longest arithmetic subsequence .(k ∈ {0, 1})
State shift ：
Updated with the previous position f[] To update the current location .

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;

Code：

class Solution {
    
/*  Here's the thing to watch out for , If a[i]+j There is no such thing as , Then it can be used f[a[i]+j][j] To update as 1; But if a[i]-j There is no such thing as , And negative numbers , This f[a[i]-j] It will not be updated to 1, Still for 0, There will be errors . Therefore, this situation should be judged as 1.  In addition, you can't use max(0, a[i]-j) To update , Because in this problem f[0] There is a value , Not always for 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;
    }
};

Ideas 2：dp,O(n^2)

An arithmetic sequence requires at least two adjacent positions to determine , Therefore, we can define a two-dimensional state to represent the longest length of the arithmetic sequence with these two positions as the end positions .
State definition ：
Definition f[i, j] Express , With i, j These two positions are the longest length of the isochronous sequence of the end position .

State shift ：f[i][j] = f[mp[2*a[i]-a[j]]][i] + 1,mp[x] To get the value x Where it appears in front .
update , For the current location i, Traverse all positions behind it j, Calculate the front position through these two values k. Use the front one f[k, i] To update the following f[i, j].

Here's another trick , From the current value and the values enumerated later, you can calculate the value of the previous position of the arithmetic sequence , But how to find the position of the value in the array ？
It can be used directly map Mark , Mark the position where the value last appeared .
（ The last time , Can't the front position be updated ？ It's OK, too , Only the length that can be updated by the back position must not be less than that of the front position , So you can update it directly with the location of the last occurrence ）
Put the current position i After traversing , And then a[i] The position where it appears is marked i, This will ensure that mp[x] The position that appears must be before the current position , Update the following with the previous answer .

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;
    }
};

---

3、 ... and 、 Longest Fibonacci subsequence

The question
Given an inclusion $N$ Strictly increasing array of positive integers , The first of these $i$ An integer is $A_i$.
Find the length of the longest Fibonacci subsequence .（ Subsequences are not necessarily continuous in the original array ）

If the sequence $X_1,X_2,...,X_n$ Meet the following conditions , Just say it's Fibonacci Of ：

• n >= 3
• For all i + 2 <= n, There are $X_i+X_{i+1}=X_{i+2}$

Ideas 1：set violence ,O($n^{2}logm$),m by Ai Maximum

Save the entire array to set in , Double loop traverses the first two positions of the sequence , For every two initial positions , Get the position of the next number .set Judge whether it exists , Length of existence ++, Location update , Keep walking back .
Because it is strictly increasing , And the series grows in Fibonacci , The longest is 43 term , So the overall complexity is O($n^{2}logm$).
（ Because it is monotonically increasing , Very clever use set Come on ）

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;
    }
};

Ideas 2：dp,O(n^2)

The idea is the same as the second solution of the previous problem .
State definition ：
Definition f[i, j] Express , With i, j The longest length of Fibonacci subsequence with position as the end position .
State shift ：
f[i][j] = f[mp[2*a[i]-a[j]]][i] + 1, among mp[x] Indicated value x In the current position i Where the front appears .
For the current location i As the number sequence 2 term , Traverse all the following positions j As the number sequence 3 term , From the values of these two positions, calculate the 1 Item value ,mp[x] Get its position k.
By position k and i Determine the sequence of numbers to be updated by the location i and j Definite sequence .
Again , In order to ensure mp[x] Is in the current position i Previous , After traversing the current position i Position added to map in .
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;
    }
};

From this we can see that , Ideas 2 It is universal for solving such subsequence problems , Should be skilled in memory .