題目： LeetCode - 1218. Longest Arithmetic Subsequence of Given Difference

題目說明

給一個陣列和一個整數 difference，求差為 difference 之最長等差子序列長度。

解題思路

明顯 DP 題，dp[i] 表以 arr[i] 結尾之最長子序列長度，雙迴圈 i, j 遍歷，j 為 0 ~ i - 1，若 arr[j] - arr[i] 為 difference 表 arr[j] 是可以接在以 arr[i] 為結尾之最長子序列後面，轉移方程為 dp[i] = max(dp[j] + 1, dp[i]);，但這個做法會超時。

上網參考後發現由於這題給定 difference 了，因此當遍歷到 arr[i] 時只需要看 arr[i] - difference 這個數字是否出現過即可，dp[n] 表示以 n 結尾之最長子序列長度，轉移方程為 dp[n] = dp[n - difference] + 1;。

參考解法

TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int mx = 1;
        vector<int> dp(arr.size(), 1);
        for (int i = 0; i < arr.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[i] - arr[j] == difference) {
                    dp[i] = max(dp[i], dp[j] + 1);
                    mx = max(dp[i], mx);
                }
            }
        }
        return mx;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int mx = 1;
        unordered_map<int, int> dp;
        for (const auto& n : arr) {
            dp[n] = dp[n - difference] + 1;
            mx = max(dp[n], mx);
        }
        return mx;
    }
};

參考資料

[LeetCode] 1218. Longest Arithmetic Subsequence of Given Difference 最长定差子序列 - Grandyang - 博客园