Sponsored
Sponsored
This approach uses a hash map (or dictionary) to keep track of the longest subsequence length that can be achieved ending with a specific value. For each element in the array, we check if there is an arithmetic subsequence ending with the element minus the given difference. If such a subsequence exists, we calculate the current subsequence length. Otherwise, we start a new subsequence from this element.
Time Complexity: O(n), where n is the length of arr. We iterate over the array once.
Space Complexity: O(n), where n is the number of distinct elements in arr stored in the dictionary.
1#include <stdio.h>
2#include <stdlib.h>
3
4#define TABLE_SIZE 20001
5
6int hash(int key) {
7 return (key + 10000) % TABLE_SIZE;
8}
9
10int longestSubsequence(int* arr, int arrSize, int difference) {
11 int* dp = (int*)calloc(TABLE_SIZE, sizeof(int));
12 int max_length = 0;
13 for (int i = 0; i < arrSize; ++i) {
14 int num = arr[i];
15 int key = hash(num);
16 int prev_key = hash(num - difference);
17 dp[key] = dp[prev_key] + 1;
18 if (dp[key] > max_length) {
19 max_length = dp[key];
20 }
21 }
22 free(dp);
23 return max_length;
24}This C solution adopts a simplistic hashing approach to simulate a map-like storage using an array and a hash function. We track subsequences using indices calculated from our hash function.
This approach utilizes an array to store information about each possible element value scaled according to the constraints. For each element in arr, determine if there is a previous subsequence that can be extended using direct array access.
Time Complexity: O(n), where n is the length of arr.
Space Complexity: O(1) (constant size array mentioned in constraints).
public class Solution {
public int LongestSubsequence(int[] arr, int difference) {
int[] dp = new int[20001];
int offset = 10000;
int max_length = 0;
foreach (int num in arr) {
int idx = num + offset;
int prev_idx = num - difference + offset;
dp[idx] = dp[prev_idx] + 1;
max_length = Math.Max(max_length, dp[idx]);
}
return max_length;
}
}This C# solution aligns indices to fixed array positions using calculated offsets to enhance direct value access, resulting in rapid sequence length calculations without extra storage overhead.