Longest non-decreasing Subsequence with adjoining variations

By
Sohaib
-
0
9
Adv1


Adv2

Given an array arr[] of N components, the duty is to seek out the size of the longest non-decreasing subsequence such that the variations between adjoining components are non-decreasing. For indices i, j, and okay: 
i < j < okay, ai − aj ≤ aj − ak

Examples:

Enter: N = 9, arr[] = [1, 3, 5, 4, 7, 8, 10, 6, 9]
Output: 6
Rationalization: Longest non-decreasing Subsequence is [1, 3, 5, 7, 8, 10]. Right here, the subsequence satisfies the given situation, (3 – 1) <= (5 – 3), (4 – 3) <= (5 – 4), (7 – 5) <= (8 – 7), (8 – 7) <= (10 – 8), and (10 – 8) <= (9 – 6). The size of such Longest Subsequence on this case is 6.

Enter: N = 8, arr[] = [1, 4, 5, 6, 2, 3, 8, 9]
Output: 5
Rationalization: Longest non-decreasing Subsequence with given situation is [1, 4, 6, 8, 9].

Method: To unravel the issue comply with the under concept: 

The concept is to make use of a dp array to retailer the size of such longest subsequence as much as index i of the given array. Then, we traverse the array for every index i, and for every index j (0 ≤ j < i), we test if the subsequence [j, i] varieties a subsequence. If it does, we replace the worth of dp[i] with the utmost worth of dp[j]+1. Lastly, we return the utmost worth within the dp array.

Beneath are the steps for the above strategy:

  • Initialize a variable say n to retailer the scale of the enter array arr.
  • Verify if the scale of the given array is lower than or equal to 2, and return the scale of the array.
  • Initialize an array dp of dimension n  all 0’s.
  • Initialize the primary two values of the dp to 1 and a couple of respectively.
  • Initialize a variable say ans = 2.
  • Iterate from index i = 2 to i < n,
    • Contained in the for loop, run one other loop from index j = 1 to j < i
      • Verify if the present ingredient and the earlier ingredient kind a subsequence with the given situation, if (arr[i] – arr[j] == arr[j] – arr[j-1]),
      • Replace the dp[] array with the utmost worth between the present dp worth of i and dp worth of j + 1.
    • Replace the ans variable with the utmost worth between itself and the present dp worth of i.
  • Return ans.

Beneath is the implementation for the above strategy:

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int longest_subsequence(vector<int> arr)

{

  

    int n = arr.dimension();

  

    

    

    if (n <= 2)

        return n;

  

    

    int dp[n];

    memset(dp, 0, sizeof(dp));

  

    

    

    dp[0] = 1;

    dp[1] = 2;

  

    

    int ans = 2;

  

    

    for (int i = 2; i < n; i++) {

  

        

        for (int j = 1; j < i; j++) {

  

            

            

            

            if (arr[i] - arr[j] == arr[j] - arr[j - 1])

  

                

                dp[i] = max(dp[i], dp[j] + 1);

        }

  

        

        ans = max(ans, dp[i]);

    }

  

    

    return ans;

}

  

int predominant()

{

    vector<int> arr = { 1, 2, 3, 5, 6, 8 };

  

    

    cout << "Longest Subsequence: "

         << longest_subsequence(arr) << endl;

    return 0;

}

Java

import java.util.Arrays;

  

public class LongestConvexSubsequence {

    public static int longestConvexSubsequence(int[] arr)

    {

        int n = arr.size;

        

        if (n <= 2)

            return n;

  

        

        int[] dp = new int[n];

        Arrays.fill(dp, 2);

  

        

        int ans = 2;

        for (int i = 2; i < n; i++) {

            for (int j = 1; j < i; j++) {

                

                if (arr[i] - arr[j] == arr[j] - arr[j - 1])

                    dp[i] = Math.max(dp[i], dp[j] + 1);

            }

            ans = Math.max(ans, dp[i]);

        }

        return ans;

    }

  

    

    public static void predominant(String[] args)

    {

        int[] arr = { 1, 2, 3, 5, 6, 8 };

        System.out.println("Longest Convex Subsequence: " + longestConvexSubsequence(arr));

    }

}

Python3

  

def longest_convex_subsequence(arr):

    n = len(arr)

   

    if n <= 2:

        return n

     

    dp = [2] * n

  

    

    ans = 2

    

    for i in vary(2, n):

      

        for j in vary(1, i):

          

            if arr[i] - arr[j] == arr[j] - arr[j-1]:

              

                dp[i] = max(dp[i], dp[j] + 1)

        

        ans = max(ans, dp[i])

  

  

    return ans

  

arr = [1, 2, 3, 5, 6, 8]

print("Longest Convex Subsequence: ", longest_convex_subsequence(arr))
Output

Longest Subsequence: 3

Time Complexity: O(n2)
Auxiliary Area: O(n), the place n is the size of the given array.

Grasping Method: To unravel the issue comply with the under concept:

The concept is to make use of a variable ‘len’ to retailer the size of the longest subsequence seen to this point, and one other variable ‘curr_len’ to retailer the size of the present subsequence. Additionally, use a variable ‘diff’ to retailer the distinction between two consecutive components of the present subsequence. Initialize ‘len’ and ‘curr_len’ with 2, as any two components kind a subsequence. Traverse the array and test if the distinction between two consecutive components is similar because the ‘diff’ variable, increment ‘curr_len’, else, replace the ‘len’ variable with the utmost worth between ‘len’ and ‘curr_len’, and reset ‘curr_len’ to 2, and ‘diff’ to the distinction between the 2 consecutive components. Return the utmost worth between ‘len’ and ‘curr_len’.

Beneath are the steps for the above strategy:

  • Initialize a variable say n to retailer the scale of the enter array arr.
  • Verify if the scale of the given array is lower than or equal to 2, and return the scale of the array.
  • Initialize a variable len = 2, because the size of the smallest subsequence, is 2.
  • Initialize a variable diff to the distinction between the second and the primary components of the enter array arr.
  • Initialize the present size of subsequence as 2, curr_len = 2.
  • Traverse the array from index i = 2 to i < n and test if the distinction between the present ingredient and the earlier ingredient is similar because the distinction between the earlier two components, increment curr_length by 1.
  • Else if the distinction between the present ingredient and the earlier ingredient is just not the identical because the distinction between the earlier two components, replace the distinction between the consecutive components, diff = arr[i] – arr[i-1].
  • Replace size of longest subsequence, len = max(len, curr_len).
  • The present size of the subsequence is reset to 2.
  • As soon as the for loop completes, the size of the longest subsequence is up to date by taking the utmost worth between itself and the present size of the subsequence, len = max(len, curr_len).
  • Return the worth of variable len.

Beneath is the implementation for the above strategy:

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int longest_subsequence(vector<int> arr)

{

    int n = arr.dimension();

  

    

    

    

    

    if (n <= 2)

        return n;

  

    

    

    int len = 2;

  

    

    

    int diff = arr[1] - arr[0];

  

    

    

    int curr_len = 2;

  

    

    for (int i = 2; i < n; i++) {

  

        

        

        

        

        

        if (arr[i] - arr[i - 1] == diff) {

  

            

            

            curr_len++;

        }

        else {

  

            

            

            

            diff = arr[i] - arr[i - 1];

  

            

            

            len = max(len, curr_len);

  

            

            

            

            curr_len = 2;

        }

    }

  

    

    

    len = max(len, curr_len);

  

    

    

    return len;

}

  

int predominant()

{

    vector<int> arr = { 1, 2, 3, 5, 6, 8 };

  

    

    cout << "Longest non-decreasing Subsequence: "

         << longest_subsequence(arr) << endl;

    return 0;

}

Java

  

import java.util.Arrays;

  

public class LongestConvexSubsequence {

    public static int longestConvexSubsequence(int[] arr)

    {

        int n = arr.size;

  

        

        if (n <= 2)

            return n;

  

        

        int len = 2;

        int diff = arr[1] - arr[0];

        int curr_len = 2;

  

        

        for (int i = 2; i < n; i++) {

  

            

            if (arr[i] - arr[i - 1] == diff) {

                curr_len++;

            }

            else {

                

                diff = arr[i] - arr[i - 1];

                len = Math.max(len, curr_len);

                curr_len = 2;

            }

        }

  

        len = Math.max(len, curr_len);

        return len;

    }

  

    

    public static void predominant(String[] args)

    {

        int[] arr = { 1, 2, 3, 5, 6, 8 };

        System.out.println("Longest Convex Subsequence: " + longestConvexSubsequence(arr));

    }

}

Python3

  

def longest_convex_subsequence(arr):

    n = len(arr)

    

    if n <= 2:    

        return n

  

    

    max_len = 2   

    

    diff = arr[1] - arr[0]   

    

    curr_len = 2  

    

    for i in vary(2, n):  

      

        if arr[i] - arr[i-1] == diff: 

          

            curr_len += 1   

        

        else:  

          

            diff = arr[i] - arr[i-1]   

            

            max_len = max(max_len, curr_len)  

            

            curr_len = 2   

     

    max_len = max(max_len, curr_len)

    

    return max_len   

  

arr = [1, 2, 3, 5, 6, 8]   

print("Longest Convex Subsequence: ", longest_convex_subsequence(arr))   
Output

Longest non-decreasing Subsequence: 3

Time Complexity: O(n), the place n is the size of the given array.
Auxiliary Area: O(1), since we aren’t utilizing any extra information buildings.

Adv3