LeetCode 1027. 最长等差数列

[yinxin630]

题目

https://leetcode-cn.com/problems/longest-arithmetic-sequence/

思路

1. 动态规划, dp[i][diff] 表示以第 i 个数结尾, 并且差值为 diff 的等差数列长度
2. 对于第 i 个数字
   1. 遍历 j = [0, i - 1] 的数字, 求diff
   2. 如果 dp[j][diff] 存在, 则 dp[i][diff] 取自身和 dp[j][diff] + 1 中较大的那个
   3. 如果 dp[i][diff] 不存在, 则 dp[i][diff] = 2, 因为 j 和 i 构成一个等差数列
   4. 判断 dp[i][diff] 是否大于 max, 大于则更新

代码

/**
 * @param {number[]} A
 * @return {number}
 */
var longestArithSeqLength = function(A) {
    if (A.length <= 2) {
        return A.length;
    }

    const dp = {};
    function get(x, y) {
        return dp[x] && dp[x][y];
    }
    function set(x, y, value) {
        dp[x] = dp[x] || {};
        dp[x][y] = value;
    }

    let max = 2;
    for (let i = 1; i < A.length; i++) {
        for (let j = 0; j < i; j++) {
            const diff = A[i] - A[j];

            if (get(j, diff)) {
                set(i, diff, Math.max(
                    get(i, diff) || 0,
                    get(j, diff) + 1
                ));
            }

            if (!get(i, diff)) {
                set(i, diff, 2);
            }

            max = Math.max(max, get(i, diff));
        }
    }

    return max;
};