Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1027.html
1027. Longest Arithmetic Sequence (Medium)
Given an array A
of integers, return the length of the longest arithmetic subsequence in A
.
Recall that a subsequence of A
is a list A[i_1], A[i_2], ..., A[i_k]
with 0 <= i_1 < i_2 < ... < i_k <= A.length - 1
, and that a sequence B
is arithmetic if B[i+1] - B[i]
are all the same value (for 0 <= i < B.length - 1
).
Example 1:
Input: [3,6,9,12] Output: 4 Explanation: The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: [9,4,7,2,10] Output: 3 Explanation: The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: [20,1,15,3,10,5,8] Output: 4 Explanation: The longest arithmetic subsequence is [20,15,10,5].
Note:
2 <= A.length <= 2000
0 <= A[i] <= 10000
Related Topics:
Dynamic Programming
Solution 1. DP
// OJ: https://leetcode.com/problems/longest-arithmetic-sequence/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
unordered_map<int, unordered_map<int, int>> m;
int ans = 0;
for (int n : A) {
m[n] = {};
for (auto &p : m) {
int d = n - p.first;
ans = max(ans, m[n][d] = p.second.count(d) ? p.second[d] + 1 : 2);
}
}
return ans;
}
};
-
class Solution { public int longestArithSeqLength(int[] A) { if (A == null) return 0; int length = A.length; if (length <= 2) return length; int maxLength = 2; Map<Integer, TreeSet<Integer>> numIndicesMap = new HashMap<Integer, TreeSet<Integer>>(); for (int i = 0; i < length; i++) { int num = A[i]; TreeSet<Integer> indices = numIndicesMap.getOrDefault(num, new TreeSet<Integer>()); indices.add(i); numIndicesMap.put(num, indices); if (indices.size() > maxLength) maxLength = indices.size(); } for (int i = 0; i < length; i++) { int num1 = A[i]; for (int j = i + 1; j < length; j++) { int num2 = A[j]; int difference = num2 - num1; if (difference == 0) continue; int curLength = 2; int prevIndex = j; int prevNum = num2; while (true) { int curNum = prevNum + difference; TreeSet<Integer> indices = numIndicesMap.getOrDefault(curNum, new TreeSet<Integer>()); Integer curIndex = indices.ceiling(prevIndex); if (curIndex == null) break; curLength++; prevIndex = curIndex; prevNum = curNum; } maxLength = Math.max(maxLength, curLength); } } return maxLength; } } ############ class Solution { public int longestArithSeqLength(int[] nums) { int n = nums.length; int ans = 0; int[][] f = new int[n][1001]; for (int i = 1; i < n; ++i) { for (int k = 0; k < i; ++k) { int j = nums[i] - nums[k] + 500; f[i][j] = Math.max(f[i][j], f[k][j] + 1); ans = Math.max(ans, f[i][j]); } } return ans + 1; } }
-
// OJ: https://leetcode.com/problems/longest-arithmetic-sequence/ // Time: O(N^2) // Space: O(N^2) class Solution { public: int longestArithSeqLength(vector<int>& A) { unordered_map<int, unordered_map<int, int>> m; int ans = 0; for (int n : A) { m[n] = {}; for (auto &p : m) { int d = n - p.first; ans = max(ans, m[n][d] = p.second.count(d) ? p.second[d] + 1 : 2); } } return ans; } };
-
class Solution: def longestArithSeqLength(self, nums: List[int]) -> int: n = len(nums) dp = [[1] * 1001 for _ in range(n)] ans = 0 for i in range(1, n): for j in range(i): d = nums[i] - nums[j] + 500 dp[i][d] = max(dp[i][d], dp[j][d] + 1) ans = max(ans, dp[i][d]) return ans ############ # 1027. Longest Arithmetic Subsequence # https://leetcode.com/problems/longest-arithmetic-subsequence/ class Solution: def longestArithSeqLength(self, nums: List[int]) -> int: dp = {} n = len(nums) for i in range(n): for j in range(i + 1, n): dp[(j, nums[j] - nums[i])] = dp.get((i, nums[j] - nums[i]), 1) + 1 return max(dp.values())
-
func longestArithSeqLength(nums []int) int { n := len(nums) f := make([][]int, n) for i := range f { f[i] = make([]int, 1001) } ans := 0 for i := 1; i < n; i++ { for k := 0; k < i; k++ { j := nums[i] - nums[k] + 500 f[i][j] = max(f[i][j], f[k][j]+1) ans = max(ans, f[i][j]) } } return ans + 1 } func max(a, b int) int { if a > b { return a } return b }
-
function longestArithSeqLength(nums: number[]): number { const n = nums.length; let ans = 0; const f: number[][] = Array.from({ length: n }, () => new Array(1001).fill(0), ); for (let i = 1; i < n; ++i) { for (let k = 0; k < i; ++k) { const j = nums[i] - nums[k] + 500; f[i][j] = Math.max(f[i][j], f[k][j] + 1); ans = Math.max(ans, f[i][j]); } } return ans + 1; }