【leetcode】1027. Longest arithmetic sequence (dynamic programming)

subject ：

1027.  The longest arithmetic sequence 
 Give you an array of integers  nums, return  nums  The length of the longest isochromatic subsequence in .
 Think about it ,nums  The subsequence of is a list  nums[i1], nums[i2], ..., nums[ik] , And  0 <= i1 < i2 < ... < ik <= nums.length - 1. And if the  seq[i+1] - seq[i]( 0 <= i < seq.length - 1)  It's all the same , So sequence  seq  It's equal difference .

 Example  1：

 Input ：nums = [3,6,9,12]
 Output ：4
 explain ： 
 The whole array has a tolerance of  3  Equal difference sequence of .
 Example  2：

 Input ：nums = [9,4,7,2,10]
 Output ：3
 explain ：
 The longest isochromatic subsequence is  [4,7,10].
 Example  3：

 Input ：nums = [20,1,15,3,10,5,8]
 Output ：4
 explain ：
 The longest isochromatic subsequence is  [20,15,10,5].
 
 Tips ：

2 <= nums.length <= 1000
0 <= nums[i] <= 500

Dynamic programming ：

Ideas :
1. Definition DP Array
dp[i][d]: It means the first one i Number , The difference from the previous number is d when , The length of the longest arithmetic sequence that can be formed .
We can get the equation of state transition ：dp[i][d] = max(dp[i][d],dp[j][d]+1), among 0<=j<i.
2. Element difference d It means
Because the array element size is 0<=nums[i]<=500, So in the array The range of the difference between the two elements is -500<= d<=500.
therefore , have access to d+500 Map the difference to [0,1000] It is convenient for us to define dp Array .

• Time complexity ：O(n^{2})
• Spatial complexity ：O(n*d)

class Solution {
    
    public int longestArithSeqLength(int[] nums) {
    
        int len = nums.length;
        if(len == 0) return 0; 
        int res = 0;
        int[][]dp = new int[len][1001];
        for(int i = 0; i < len;i++){
    
            for(int j = 0; j < i;j++){
    
                // nums[i] Make a difference with all the previous numbers 
                int d = nums[i] - nums[j] + 500;
                dp[i][d] = Math.max(dp[i][d],dp[j][d] + 1);
                res = Math.max(res,dp[i][d]);  
            }
        }
        // On initialization  int[][] dp = new int[n][1010]; The default value of the element is  0, The first element of the arithmetical sequence is not included . Therefore return res+1.
		// If it is initialized to  1, Return directly later ans
        return res + 1;
    }
}