1027. Longest Arithmetic Subsequence

題目描述

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Note that:

• A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
• A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

範例

Example 1:

Input: nums = [3,6,9,12]
Output: 4
Explanation:  The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

Input: nums = [9,4,7,2,10]
Output: 3
Explanation:  The longest arithmetic subsequence is [4,7,10].

Example 3:

Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation:  The longest arithmetic subsequence is [20,15,10,5].

Constraints:

• 2 <= nums.length <= 1000
• 0 <= nums[i] <= 500

解答

Python

放假很閒，嘗試各種優化
Yen-Chi ChenFri, Jun 23, 2023

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2:
            return n

        dp = [defaultdict(lambda: 1) for _ in range(n)]
        ans = 0
        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                dp[i][diff] = dp[j][diff] + 1
                ans = max(ans, dp[i][diff])
        return ans

Runtime 3391 ms Beats 39.18%
Yen-Chi ChenFri, Jun 23, 2023

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        dp = {}
        for i in range(len(nums)):
            for j in range(i):
                diff = nums[i] - nums[j]
                if (j, diff) in dp:
                    dp[i, diff] = dp[j, diff] + 1
                else:
                    dp[i, diff] = 2
        return max(dp.values())

Runtime 2825 ms Beats 80.4%
Yen-Chi ChenFri, Jun 23, 2023

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        upper = max(nums)
        n = len(nums)
        ans = 0
        for diff in range(-upper, upper + 1):
            dp = defaultdict(int)
            for num in nums:
                dp[num] = dp[num - diff] + 1
            ans = max(ans, max(dp.values()))
        return ans

Runtime 2055 ms Beats 90.59%
Yen-Chi ChenFri, Jun 23, 2023

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        extent = max(nums) - min(nums)
        n = len(nums)
        ans = 2
        for D in range(extent + 1):
            if D * (ans - 1) >= extent:
                break
            for diff in [-D, D]:
                dp = defaultdict(int)
                for num in nums:
                    dp[num] = dp[num - diff] + 1
                ans = max(ans, max(dp.values()))
        return ans

Runtime 215 ms Beats 100%
Yen-Chi ChenFri, Jun 23, 2023

C++

class Solution {
public:
    const int MAX_NUM = 500;
    int longestArithSeqLength(vector<int>& nums) {
        ios_base::sync_with_stdio(0); cin.tie(0);
        int n = nums.size();
        int ans = 0;
        // unordered_map<pair<int, int>, int, hash_pair> dp;
        vector<vector<int>> dp(n + 10, vector(1000 + 10, 0));
        // vector<unordered_map<int, int>> dp(n + 10);
        for (int right = 1; right < n; right ++) {
            for (int left = 0; left < right; left ++) {
                int numDiff = nums[right] - nums[left] + MAX_NUM;
                dp[right][numDiff] = dp[left][numDiff] + 1;
                ans = max(ans, dp[right][numDiff]);
            }
        }
        return ans + 1;
    }
};

Jerry23 June, 2023

Reference

回到題目列表