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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LongestSubsequence(int[] arr, int difference) {
6 Dictionary<int, int> dp = new Dictionary<int, int>();
7 int max_length = 0;
8 foreach (int num in arr) {
9 if (!dp.ContainsKey(num)) dp[num] = 0;
10 dp[num] = dp.GetValueOrDefault(num - difference, 0) + 1;
11 max_length = Math.Max(max_length, dp[num]);
12 }
13 return max_length;
14 }
15}A C# solution using a Dictionary, where each iteration updates subsequences by checking the possible previous number that can form a valid arithmetic sequence.
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.