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 <stdio.h>
2#include <string.h>
3
4int longestArithSeqLength(int* nums, int numsSize) {
5 if (numsSize <= 2) return numsSize;
6 int dp[numsSize][1001]; // Adjust for [-500, 500] difference range
7 memset(dp, 0, sizeof(dp));
8 int maxLength = 2;
9 for (int i = 0; i < numsSize; i++) {
10 for (int j = 0; j < i; j++) {
11 int diff = nums[i] - nums[j] + 500; // Shift to be positive
12 dp[i][diff] = dp[j][diff] ? dp[j][diff] + 1 : 2;
13 if (dp[i][diff] > maxLength) {
14 maxLength = dp[i][diff];
15 }
16 }
17 }
18 return maxLength;
19}
20
21int main() {
22 int nums[] = {3, 6, 9, 12};
23 int result = longestArithSeqLength(nums, 4);
24 printf("%d\n", result);
25 return 0;
26}The C solution uses a 2D array `dp` where `dp[i][diff]` stores the longest arithmetic subsequence ending at `i` with common difference `diff`. Differences are adjusted by +500 to convert negative indices to positive. This approach scans each pair of indices `(j, i)` and computes the difference between elements. If a sequence with this difference already exists ending at `j`, it is extended by `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
This Java implementation uses arrays of hashmaps to keep memory use low and operations fast by storing only active computations for each number at each step.