Maximize count of Decreasing Consecutive Subsequences from an Array

0 0 6 minutes read

Given an array arr[] consisting of N integers, the task is to find the maximum count of decreasing subsequences possible from an array that satisfies the following conditions:

Each subsequence is in its longest possible form.
The difference between adjacent elements of the subsequence is always 1.

Examples:

Input: arr[] = {2, 1, 5, 4, 3}
Output: 2
Explanation:
Possible decreasing subsequences are { 5, 4, 3 } and { 2, 1 }.
Input: arr[] = {4, 5, 2, 1, 4}
Output: 3
Explanation:
Possible decreasing subsequences are { 4 }, { 5, 4} and { 2, 1}.

Approach:
The idea is to use a HashMap to solve the problem. Follow the steps below:

Maintain a HashMap to store the count of subsequences possible for an array element and maxSubsequences to count the total number of possible subsequences.
Traverse the array, and for each element arr[i], check if any subsequence exists which can have arr[i] as the next element, by the count assigned to arr[i] in the HashMap.
If exists, do the following:
- Assign arr[i] as the next element of the subsequence.
- Decrease count assigned to arr[i] in the HashMap, as the number of possible subsequences with arr[i] as the next element has decreased by 1.
- Similarly, increase count assigned to arr[i] – 1 in the HashMap, as the number of possible subsequences with arr[i] – 1 as the next element has increased by 1.
Otherwise, increase maxCount, as a new subsequence is required and repeat the above step to modify the HashMap.
After completing the traversal of the array, print the value of maxCount.

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum number
// number of required subsequences
int maxSubsequences(int arr[], int n)
{
 
    // HashMap to store number of
    // arrows available with
    // height of arrow as key
    unordered_map<int, int> m;
 
    // Stores the maximum count
    // of possible subsequences
    int maxCount = 0;
 
    // Stores the count of
    // possible subsequences
    int count;
 
    for (int i = 0; i < n; i++) {
 
        // Check if i-th element can be
        // part of any of the previous
        // subsequence
        if (m.find(arr[i]) != m.end()) {
 
            // Count of subsequences
            // possible with arr[i] as
            // the next element
            count = m[arr[i]];
 
            // If more than one such
            // subsequence exists
            if (count > 1) {
 
                // Include arr[i] in a subsequence
                m[arr[i]] = count - 1;
            }
 
            // Otherwise
            else
                m.erase(arr[i]);
 
            // Increase count of subsequence possible
            // with arr[i] - 1 as the next element
            if (arr[i] - 1 > 0)
                m[arr[i] - 1] += 1;
        }
        else {
 
            // Start a new subsequence
            maxCount++;
 
            // Increase count of subsequence possible
            // with arr[i] - 1 as the next element
            if (arr[i] - 1 > 0)
                m[arr[i] - 1] += 1;
        }
    }
 
    // Return the answer
    return maxCount;
}
 
// Driver Code
int main()
{
 
    int n = 5;
 
    int arr[] = { 4, 5, 2, 1, 4 };
 
    cout << maxSubsequences(arr, n) << endl;
 
    // This code is contributed by bolliranadheer
}

Java

// Java program to implement 
// the above approach 
import java.util.*; 
   
class GFG { 
   
    // Function to find the maximum number 
    // number of required subsequences 
    static int maxSubsequences(int arr[], int n) 
    { 
   
        // HashMap to store number of 
        // arrows available with 
        // height of arrow as key 
        HashMap<Integer, Integer> map 
            = new HashMap<>(); 
   
        // Stores the maximum count 
        // of possible subsequences 
        int maxCount = 0; 
   
        // Stores the count of 
        // possible subsequences 
        int count; 
   
        for (int i = 0; i < n; i++) 
        { 
            // Check if i-th element can be 
            // part of any of the previous 
            // subsequence 
            if (map.containsKey(arr[i])) 
            { 
                // Count  of subsequences 
                // possible with arr[i] as 
                // the next element 
                count = map.get(arr[i]); 
   
                // If more than one such 
                // subsequence exists 
                if (count > 1) 
                { 
   
                    // Include arr[i] in a subsequence 
                    map.put(arr[i], count - 1); 
                } 
   
                // Otherwise 
                else
                    map.remove(arr[i]); 
   
                // Increase count of subsequence possible 
                // with arr[i] - 1 as the next element 
                if (arr[i] - 1 > 0) 
                    map.put(arr[i] - 1, 
                    map.getOrDefault(arr[i] - 1, 0) + 1); 
            } 
            else { 
   
                // Start a new subsequence 
                maxCount++; 
   
                // Increase count of subsequence possible 
                // with arr[i] - 1 as the next element 
                if (arr[i] - 1 > 0) 
                    map.put(arr[i] - 1, 
                    map.getOrDefault(arr[i] - 1, 0) + 1); 
            } 
        } 
   
        // Return the answer 
        return maxCount; 
    } 
   
    // Driver Code 
    public static void main(String[] args) 
    { 
        int n = 5; 
        int arr[] = { 4, 5, 2, 1, 4 }; 
        System.out.println(maxSubsequences(arr, n)); 
    } 
}

C#

// C# program to implement 
// the above approach 
using System;
using System.Collections.Generic;
  
class GFG{ 
   
// Function to find the maximum number 
// number of required subsequences 
static int maxSubsequences(int []arr, int n) 
{ 
     
    // Dictionary to store number of 
    // arrows available with 
    // height of arrow as key 
    Dictionary<int, 
               int> map = new Dictionary<int,
                                         int>(); 
                                          
    // Stores the maximum count 
    // of possible subsequences 
    int maxCount = 0;
 
    // Stores the count of 
    // possible subsequences 
    int count; 
 
    for(int i = 0; i < n; i++) 
    { 
         
        // Check if i-th element can be 
        // part of any of the previous 
        // subsequence 
        if (map.ContainsKey(arr[i])) 
        { 
             
            // Count  of subsequences 
            // possible with arr[i] as 
            // the next element 
            count = map[arr[i]]; 
 
            // If more than one such 
            // subsequence exists 
            if (count > 1) 
            { 
                 
                // Include arr[i] in a subsequence 
                map.Add(arr[i], count - 1); 
            } 
 
            // Otherwise 
            else
                map.Remove(arr[i]); 
 
            // Increase count of subsequence possible 
            // with arr[i] - 1 as the next element 
            if (arr[i] - 1 > 0) 
                if (map.ContainsKey(arr[i] - 1))
                    map[arr[i] - 1]++;
                else
                    map.Add(arr[i] - 1, 1); 
        } 
        else
        { 
             
            // Start a new subsequence 
            maxCount++; 
 
            // Increase count of subsequence possible 
            // with arr[i] - 1 as the next element 
            if (arr[i] - 1 > 0) 
                if (map.ContainsKey(arr[i] - 1))
                    map[arr[i] - 1]++;
                else
                    map.Add(arr[i] - 1, 1); 
        } 
    } 
 
    // Return the answer 
    return maxCount; 
} 
 
// Driver Code 
public static void Main(String[] args) 
{ 
    int n = 5; 
    int []arr = { 4, 5, 2, 1, 4 }; 
     
    Console.WriteLine(maxSubsequences(arr, n)); 
} 
} 
 
// This code is contributed by Amit Katiyar

Python3

# Python program to implement
# the above approach
 
from collections import defaultdict
 
# Function to find the maximum number
# number of required subsequences
def maxSubsequences(arr, n)->int:
 
    # Dictionary to store number of
    # arrows available with
    # height of arrow as key
    m = defaultdict(int)
 
    # Stores the maximum count
    # of possible subsequences
    maxCount = 0
 
    # Stores the count
    # of possible subsequences
    count = 0
 
    for i in range(0, n):
 
        # Check if i-th element can be
        # part of any of the previous
        # subsequence
        if arr[i] in m.keys():
 
            # Count of subsequences
            # possible with arr[i] as
            # the next element
            count = m[arr[i]]
 
            # If more than one such
            # subsequence exists
            if count > 1:
 
                # Include arr[i] in a subsequence
                m[arr[i]] = count - 1
 
            # Otherwise
            else:
                m.pop(arr[i])
 
            # Increase count of subsequence possible
            # with arr[i] - 1 as the next element
            if arr[i] - 1 > 0:
                m[arr[i] - 1] += 1
 
        else:
            maxCount += 1
 
            # Increase count of subsequence possible
            # with arr[i] - 1 as the next element
            if arr[i] - 1 > 0:
                m[arr[i] - 1] += 1
 
    # Return the answer
    return maxCount
 
 
# Driver Code
if __name__ == '__main__':
    n = 5
    arr = [4, 5, 2, 1, 4]
    print(maxSubsequences(arr, n))
 
# This code is contributed by Riddhi Jaiswal.

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function to find the maximum number
// number of required subsequences
function maxSubsequences(arr, n)
{
      
    // Dictionary to store number of
    // arrows available with
    // height of arrow as key
    let map = new Map();
                                           
    // Stores the maximum count
    // of possible subsequences
    let maxCount = 0;
  
    // Stores the count of
    // possible subsequences
    let count;
  
    for(let i = 0; i < n; i++)
    {
          
        // Check if i-th element can be
        // part of any of the previous
        // subsequence
        if (map.has(arr[i]))
        {
              
            // Count  of subsequences
            // possible with arr[i] as
            // the next element
            count = map[arr[i]];
  
            // If more than one such
            // subsequence exists
            if (count > 1)
            {
                  
                // Include arr[i] in a subsequence
                map.add(arr[i], count - 1);
            }
  
            // Otherwise
            else
                map.delete(arr[i]);
  
            // Increase count of subsequence possible
            // with arr[i] - 1 as the next element
            if (arr[i] - 1 > 0)
                if (map.has(arr[i] - 1))
                    map[arr[i] - 1]++;
                else
                    map.set(arr[i] - 1, 1);
        }
        else
        {
              
            // Start a new subsequence
            maxCount++;
  
            // Increase count of subsequence possible
            // with arr[i] - 1 as the next element
            if (arr[i] - 1 > 0)
                if (map.has(arr[i] - 1))
                    map[arr[i] - 1]++;
                else
                    map.set(arr[i] - 1, 1);
        }
    }
  
    // Return the answer
    return maxCount;
}
 
// Driver code
 
    let n = 5;
    let arr = [ 4, 5, 2, 1, 4 ];
      
    document.write(maxSubsequences(arr, n));
      
</script>

Output

Time Complexity: O(n)
Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!