【每日一题Day185】LC1027最长等差数列 | dp

最长等差数列【LC1027】

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。

并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

最近还挺顺手的

2023/04/22

• 思路：枚举选哪个
  每遇到一个数nums[i]，我们需要枚举这个数和前面每个数组成的等差子序列的情况（差值和长度），来更新以nums[i]结尾的差值为j的子序列的长度

1. 确定dp数组（dp table）以及下标的含义
   dp[i][j]:以nums[i]为末尾的差为j的等差序列的最长长度
   
2. 确定递推公式
   

对于dp[i][j]，枚举前一位arr[j]，求出由这nums[j],nums[i]组成的等差序列的差值div，dp[i][k]的状态由dp[j][k]更新，状态转移方程为

3. 如何初始化
   初始时，子序列只包含当前数字，因此dp数组均为1（也可以初始化为0，最后将答案+1）
   
4. 确定遍历顺序
   从小到大枚举i，然后从大到小枚举j
5. 举例推导dp数组

实现

由于差值可能为负数，最小差值为-500，因此需要统一+500

class Solution {
    public int longestArithSeqLength(int[] nums) {
        // dp[i][j] 以nums[i]为末尾的差为j的等差序列的最长长度 【负数+500】
        int n = nums.length;
        int res = 0;
        int[][] dp = new int[n][1010];
        for (int i =  0; i < n; i++){
            Arrays.fill(dp[i], 1);
        }
        for (int i = 1; i < n; i++){
            for (int j = 0; j < i; j++){
                int div = nums[i] - nums[j] + 500;
                dp[i][div] = Math.max(dp[i][div], dp[j][div] + 1);
                res = Math.max(res, dp[i][div]);
            }
        }
        return res;
    }
}

复杂度

• 时间复杂度：O(nC+n2)，n为数组长度，C为定义的状态空间大小，初始化需要的时间复杂度为O(nC)，动态规划的时间复杂度为O(n2)
• 空间复杂度：O(nC)