Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LeetCode 1027. 最长等差数列 #11

Open
yinxin630 opened this issue May 25, 2019 · 0 comments
Open

LeetCode 1027. 最长等差数列 #11

yinxin630 opened this issue May 25, 2019 · 0 comments
Labels

Comments

@yinxin630
Copy link
Owner

题目

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;
};
@yinxin630 yinxin630 changed the title 1027. 最长等差数列 LeetCode 1027. 最长等差数列 May 25, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant