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).
The C solution uses predefined arrays and simple indexing to avoid dynamic memory allocations and achieve time-efficient computations over elements in arr.