# 1027. Longest Arithmetic Subsequence

• Time: $O(n^2)$
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: int longestArithSeqLength(vector& nums) { const int n = nums.size(); int ans = 0; // dp[i][k] := length of the longest arithmetic subseq ofnums // nums[0..i] with k = diff + 500 vector> dp(n, vector(1001)); for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) { const int k = nums[i] - nums[j] + 500; dp[i][k] = max(2, dp[j][k] + 1); ans = max(ans, dp[i][k]); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int longestArithSeqLength(int[] nums) { final int n = nums.length; int ans = 0; // dp[i][k] := length of the longest arithmetic subseq ofnums // nums[0..i] with k = diff + 500 int[][] dp = new int[n][1001]; for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) { final int k = nums[i] - nums[j] + 500; dp[i][k] = Math.max(2, dp[j][k] + 1); ans = Math.max(ans, dp[i][k]); } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def longestArithSeqLength(self, nums: List[int]) -> int: n = len(nums) ans = 0 # dp[i][k] := length of the longest arithmetic subseq ofnums # nums[0..i] with k = diff + 500 dp = [[0] * 1001 for _ in range(n)] for i in range(n): for j in range(i): k = nums[i] - nums[j] + 500 dp[i][k] = max(2, dp[j][k] + 1) ans = max(ans, dp[i][k]) return ans