703290. Longest Arithmetic Subsequence
Longest Arithmetic Subsequence
Slug: longest-arithmetic-progression1019 Difficulty: Medium Id: 703290 Topic Tags: Arrays, Dynamic Programming, Data Structures, Algorithms Company Tags: Amazon, Microsoft, Snapdeal, Google
Summary
Given an array of integers, find the length of the longest arithmetic subsequence. An arithmetic progression is a sequence of numbers where each term after the first is obtained by adding a fixed constant to the previous term.
Detailed Explanation
To solve this problem, we can use dynamic programming. We initialize a 2D array dp with size n * (max_val - min_val + 1), where n is the length of the input array and max_val and min_val are the maximum and minimum values in the array, respectively.
The idea is to iterate over all possible differences between consecutive elements in the array. For each difference, we check if there's a sequence ending at that point with the same difference. If there is, we increment its length by 1. The final answer will be the maximum length of any such sequence.
Here's the step-by-step breakdown:
- Initialize
dpand set all values to 0. - Iterate over the array:
- For each element, calculate the possible differences with previous elements.
- For each difference, check if there's a sequence ending at that point with the same difference.
- If there is, increment its length by 1.
- The final answer will be the maximum length of any such sequence.
Time complexity: O(n^2) Space complexity: O(n * (max_val - min_val + 1))
Optimized Solutions
Java
public int longestArithSubseq(int[] nums) {
int n = nums.length;
int maxLen = 0;
Map<Integer, Integer> dp = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int diff = nums[i] - nums[j];
if (!dp.containsKey(diff)) {
dp.put(diff, 1);
} else {
dp.put(diff, dp.get(diff) + 1);
}
maxLen = Math.max(maxLen, dp.getOrDefault(diff, 0));
}
}
return maxLen;
}