[1027. Longest Arithmetic Subsequence](https://leetcode.com/problems/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
> 放假很閒，嘗試各種優化
> [name=Yen-Chi Chen][time=Fri, 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%
> [name=Yen-Chi Chen][time=Fri, 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%
> [name=Yen-Chi Chen][time=Fri, 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%
> [name=Yen-Chi Chen][time=Fri, 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%
> [name=Yen-Chi Chen][time=Fri, 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;
    }
};

> [name=Jerry][time=23 June, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)