最长等差数列-1027

[sl1673495]

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

回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。

 

示例 1：

输入：[3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。
示例 2：

输入：[9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。
示例 3：

输入：[20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-arithmetic-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

从后往前求 dp 的规划数组，对于每一项都要求从本项开始，一直循环到结尾，记录每个相对每个值的差的等差数列长度。

注意由于这个问题的最优解等差数列的起点不一定在第一项，所以需要在每次求解的时候都去更新全局变量 max，最后直接返回这个 max，而不是最后再对数组进行遍历求解，否则会增加复杂度。

/**
 * @param {number[]} A
 * @return {number}
 */
let longestArithSeqLength = function (A) {
    let dp = []
    let n = A.length
    if (!n) {
        return 0
    }

    let max = 0

    dp[n - 1] = { 0: 0 }

    for (let i = n - 2; i >= 0; i--) {
        dp[i] = {}
        let cur = A[i]
        for (let j = i + 1; j < n; j++) {
            let diff = A[j] - cur
            let maxLength = (dp[j][diff] || 0) + 1
            let maxIDiff = Math.max(dp[i][diff] || 0, maxLength)
            dp[i][diff] = maxIDiff
            max = Math.max(max, maxIDiff)
        }
    }

    return max + 1
};