iT邦幫忙

0

動態規劃經典題: 給定公差,在陣列中求最長的等差子序列

參考題目: leetcode- 1218. Longest Arithmetic Subsequence of Given Difference
給定公差,求最長的等差子序列。

例子:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
說明: 最長的等差子序列為 [7,5,3,1].

看更多題目,返回主頁: 系列篇章統整: 好好規劃學習動態規劃(Dynamic Programming)

假設給定的公差是d
這一題也是用DP建表格的方式(與普通的DP表格不同的是,這裡的表格是一張hashMap而不是普通的陣列),
我們用DP[i]表示以i為結尾的最長等差子序列長度,
在遍歷陣列的時候,譬如說遍歷到元素x,
這時就檢查x-d有沒有在表格DP裡面,
如果不在,
那麼以x為結尾的最長等差子序列長度只能是1,
如果在的話,那麼DP[x]就是DP[x-d]+1

語法上,hashMap相當於c++的unordered_map或python的dict

c++程式,328ms (AC)

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> DP; //令DP[i]表示以i為結尾的最長子序列長度
        int d = difference;
        for(auto x: arr){
            DP[x]= DP.find(x-d)==DP.end()? 1: 1+DP[x-d];
        }
        
        //找DP裡面最大的值
        int M = INT_MIN;
        for(auto e :DP){
            M = max(M,e.second);
        }
        return M;
    }
};

python程式,688ms (AC)

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        DP = dict() # 令DP[i]表示以i為結尾的最長子序列長度
        d = difference
        for x in arr:
            DP[x] = 1 if x-d not in DP else DP[x-d]+1
        return max(DP.values())

尚未有邦友留言

立即登入留言