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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6int longestArithSeqLength(vector<int>& nums) {
7 if (nums.size() <= 2) return nums.size();
8 vector<unordered_map<int, int>> dp(nums.size());
9 int maxLength = 2;
10 for (int i = 0; i < nums.size(); i++) {
11 for (int j = 0; j < i; j++) {
12 int diff = nums[i] - nums[j];
13 dp[i][diff] = dp[j].count(diff) > 0 ? dp[j][diff] + 1 : 2;
14 maxLength = max(maxLength, dp[i][diff]);
15 }
16 }
17 return maxLength;
18}
19
20int main() {
21 vector<int> nums = {3, 6, 9, 12};
22 cout << longestArithSeqLength(nums) << endl;
23 return 0;
24}This C++ solution uses a vector of hashmaps to store the length of arithmetic subsequences by their common differences. For each pair `(j, i)`, we calculate the difference and check if it already exists in `dp[j]`. If it does, we can extend this sequence to include `nums[i]`.
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
JavaScript provides a succinct implementation of the solution using built-in Maps, iterating through pairs of indices and managing difference-based sequence length efficiently in terms of both computation and space.