Sponsored
Sponsored
This approach involves using a 2D dynamic programming array to keep track of the lengths of arithmetic subsequences ending at different indices with various common differences. The outer loop iterates over end indices while the inner loop considers all pairs of start and end indices to update the subsequence lengths.
Time Complexity: O(n^2)
Space Complexity: O(n^2), where n is the size of the input array.
1function longestArithSeqLength(nums) {
2 if (nums.length <= 2) return nums.length;
3 let dp = Array.from({length: nums.length}, () => new Map());
4 let maxLength = 2;
5 for (let i = 0; i < nums.length; i++) {
6 for (let j = 0; j < i; j++) {
7 let diff = nums[i] - nums[j];
8 dp[i].set(diff, (dp[j].get(diff) || 1) + 1);
9 maxLength = Math.max(maxLength, dp[i].get(diff));
10 }
11 }
12 return maxLength;
13}
14
15// Example usage
16const nums = [3, 6, 9, 12];
17console.log(longestArithSeqLength(nums));The JavaScript solution uses an array of Maps to store the lengths of arithmetic subsequences keyed by their differences. It iterates through the array twice (nested loops), calculating differences and maintaining sequence lengths in the Maps.
This approach uses a simplified dynamic programming technique with HashMaps and tracks differences and their counts for each number. By leveraging HashMap structures, we manage subsequence lengths more efficiently and avoid using unnecessary space for non-existent differences.
Time Complexity: O(n^2)
Space Complexity: O(n^2) in the worst case but often much less due to sparse differences.
1#include <vector>
#include <unordered_map>
using namespace std;
int longestArithSeqLength(vector<int>& nums) {
if (nums.size() <= 2) return nums.size();
vector<unordered_map<int, int>> dp(nums.size());
int maxLength = 2;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
int diff = nums[i] - nums[j];
dp[i][diff] = (dp[j].count(diff) ? dp[j][diff] : 1) + 1;
maxLength = max(maxLength, dp[i][diff]);
}
}
return maxLength;
}
int main() {
vector<int> nums = {9, 4, 7, 2, 10};
cout << longestArithSeqLength(nums) << endl;
return 0;
}The C++ solution leverages STL unordered_maps to efficiently track existing differences for establishing new arithmetic subsequences, enhancing the time efficiency over the naive DP approach.