|
Given an array arr[] of N integers and an integer D, the task is to find the length of the longest non-decreasing subsequence such that the difference between every adjacent element is less than D.
Examples:
Input: arr[] = {1, 3, 2, 4, 5}, D = 2
Output: 3
Explanation:
Consider the subsequence as {3, 4, 5}, which is of maximum length = 3 satisfying the given criteria.
Input: arr[] = {1, 5, 3, 2, 7}, D = 2
Output: 2
Approach: The given problem is a variation of Longest Increasing Subsequence with criteria for the difference between adjacent array elements as less than D, this idea can be implemented using Dynamic Programming. Follow the steps below to solve the given problem:
- Initialize a dp array, where dp[i] will store the maximum length of non-decreasing subsequence after including the ith element such that the difference between every adjacent pair of elements is less than D.
- Initialize all values of the array dp[] as 1.
- Iterate a loop over the range [0, N] and in each iteration, i traverse the given array arr[] over the range [0, i – 1] using the variable j and if the value of arr[j] is at least arr[i] and the difference between them is less than D, then update the value of dp[i] to the maximum of dp[i] and (1 + dp[j]).
- After completing the above steps, print the maximum value of the array dp[] as the result.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int longestSubsequence(vector<int> arr,
int d)
{
int n = arr.size();
vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] - d < arr[j]
and arr[i] >= arr[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(
dp.begin(), dp.end());
}
int main()
{
vector<int> arr = { 1, 3, 2, 4, 5 };
int D = 2;
cout << longestSubsequence(arr, D);
return 0;
}
|
Java
import java.util.*;
public class GFG {
static int longestSubsequence(int []arr,
int d)
{
int n = arr.length;
int []dp = new int[n];
for(int i = 0; i < n ; i++)
dp[i] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] - d < arr[j] && arr[i] >= arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
Arrays.sort(dp);
return dp[n - 1];
}
public static void main (String[] args) {
int arr[] = { 1, 3, 2, 4, 5 };
int D = 2;
System.out.println(longestSubsequence(arr, D));
}
}
|
Python3
def longestSubsequence(arr, d):
n = len(arr)
dp = [1 for _ in range(n)]
for i in range(0, n):
for j in range(0, i):
if (arr[i] - d < arr[j] and arr[i] >= arr[j]):
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
if __name__ == "__main__":
arr = [1, 3, 2, 4, 5]
D = 2
print(longestSubsequence(arr, D))
|
C#
using System;
public class GFG {
static int longestSubsequence(int []arr,
int d)
{
int n = arr.Length;
int []dp = new int[n];
for(int i = 0; i < n ; i++)
dp[i] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] - d < arr[j] && arr[i] >= arr[j]) {
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
}
Array.Sort(dp);
return dp[n - 1];
}
public static void Main (string[] args) {
int []arr = { 1, 3, 2, 4, 5 };
int D = 2;
Console.WriteLine(longestSubsequence(arr, D));
}
}
|
Javascript
<script>
function longestSubsequence(arr, d)
{
let n = arr.length;
let dp = new Array(n).fill(1);
for (let i = 0; i < n; i++)
{
for (let j = 0; j < i; j++)
{
if (arr[i] - d < arr[j] && arr[i] >= arr[j])
{
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return dp.sort((a, b) => b - a)[0];
}
let arr = [1, 3, 2, 4, 5];
let D = 2;
document.write(longestSubsequence(arr, D));
</script>
|
Time Complexity: O(N2)
Auxiliary Space: O(N)
|
