1027. 最长等差数列：值域 DP.md

题目简述：

给你一个整数数组 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 是等差的。

提示：

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

题目链接：1027. 最长等差数列

思路

看到这个数据范围，我就想到很可能需要设计一种 $O(n^2)$ 或 $O(1000n)$ 时间复杂度的算法，由此我想到动态规划，因为这属于 “条件下最长子序列” 的问题，是一种比较典型的可以尝试动态规划求解的问题。进一步的，题目给定了数组内元素的取值范围 0 <= nums[i] <= 500，因此想到值域 DP。当然，如果未限定值域，也可以用哈希表处理。

因为一个等差数列的下一个元素的值是什么完全由上一个元素的值与数列的公差惟一决定，因此我想到设 $dp[num][d]$ 表示最后以 $num$ 作为目前最后一个值、公差为 $d$ 的等差数列的长度。对于每一个新扫描到的 $num$，我们都尝试遍历所有可能的公差 $d$ 以将 $num$ 作为某个限制条件下最长等差数列的最后一个元素以尝试更新 $dp[num][d]$，

• 如果 $d$ 使得该等差数列可能存在上一个元素，即 $num-d$ 在 0 <= nums[i] <= 500 范围内，则 $$ dp[num][d]=\max\big{dp[num][d],\ dp[num-d][d]+1\big} $$ 由此我们也可以推导此时 $d$ 的取值范围应满足 $0\leqslant num-d\leqslant500$，即 $d\geqslant num-500$ 且 $d\leqslant num$；

• 对于其他情况，由于 $d$ 实际上可以取到 $[-500,500]$ 内的任何值，只不过当 $d$ 不满足 $0\leqslant num-d\leqslant500$ 时以 $num$ 为最后一个元素、以 $d$ 为公差的等差数列不存在上一个元素，所以这种情况下令 $dp[num][d]=1$ 即可，表示 $num$ 是该数列的首个元素。

  注意这里不能取 dp[num][d]++，否则会造成重复计数，因为无论数组的前面还存着几个值为 $num$ 的元素，这时以 $num$ 为最后一个元素、以 $d$ 为公差的等差数列至多只能包含一个元素，例如 $num=-450$、$d=100$，上一个元素的值 $num-d=-550$ 已经超出了数组内元素的取值范围，这是不可能的。这种情况下必须记 $dp[num][d]=1$，无论更新前 $dp[num][d]$ 是 $0$ 还是已经是 $1$。

代码

算法的时间复杂度为 $O(1000n)$，空间复杂度为 $O(500\times1000)$。

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[500 + 1][1000 + 1];
        int res = 0;

        for (int num : nums) {
            for (int d = -500; d <= 500; d++) {
                if (d >= num - 500 && d <= num) {
                    dp[num][d + 500] = Math.max(dp[num][d + 500], dp[num - d][d + 500] + 1);
                } else {
                    dp[num][d + 500] = 1;
                }
                res = Math.max(res, dp[num][d + 500]);
            }
        }

        return res;
    }
}