想要精通算法和SQL的成长之路 - 最长等差数列

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 最长等差数列

原题链接

思路：

1. 我们假设dp[i][j] 为：以num[i]为结尾，以j为公差的最长等差子序列的长度。由此可知，我们的代码存在2个循环。
2. 外层循环，针对nums的每一个元素（下标为i），将其视为最长等差子序列的结尾元素。
3. 内层循环，针对[0，i)这个范围的元素，求得每种公差的最长等差子序列长度。此时二层循环下标索引为k，计算出每个元素和当前num[i]之间的公差：j。
4. 即有：dp[i][j] = Max(dp[i][j], dp[k][j] + 1)。
5. 同时我们用一个全局变量res，不断地更新它的最大值即可。res = Math.max(res, dp[i][j]);

注意的点：

1. 考虑到公差为负数的情况，那么结合题目本身，我们可以发现公差的范围是[-500,500]，为了避免下标越界，我们统一把公差的值转为正数。即公差统一加上500，那么范围是[0,1000]。我们就可以初始化动态规划数组： int[][] dp = new int[nums.length][1001];
2. 如果我们没有给数组的所有可能初始化为1（单个元素自身也可成为一个子数组，长度为1），我们只需要返回结果+1即可。

最终代码如下：

public class Test1027 {
    public int longestArithSeqLength(int[] nums) {
        int res = Integer.MIN_VALUE;
        int[][] dp = new int[nums.length][1001];
        for (int i = 1; i < nums.length; i++) {
            for (int k = 0; k < i; k++) {
                // 公差统一+500
                int j = nums[i] - nums[k] + 500;
                // 更新[0,i) 中，所有以 j 为公差 的最长子序列长度，同时更新dp[i][j]
                dp[i][j] = Math.max(dp[i][j], dp[k][j] + 1);
                // 更新最大值
                res = Math.max(res, dp[i][j]);
            }
        }
        return res + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17