LeetCode

LeetCode 1218. Longest Arithmetic Subsequence of Given Difference 题解

查阅更多的题解,请点击
GitHub传送门

Problem

1218. Longest Arithmetic Subsequence of Given Difference

Solution

DP, O(n) time

題目是求最长的等差序列,利用dp求解,假设前i个数我们已经得到解,那么加入第i+1个数x,若x-difference在前i个数中存在,那么更新之前候选序列;若不存在,x可以作为一个新的候选序列的开头

class Solution
{
public:
    int longestSubsequence(vector &arr, int difference)
    {

        unordered_map forwards;
        int res = 0;
        for (auto item : arr)
        {
            if (forwards.count(item - difference))
            {
                forwards[item] = forwards[item - difference] + 1;
                res = max(res, forwards[item]);
            }
            else
            {
                forwards[item] = 1;
            }
        }
        return res == 0 ? 1 : res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注