Given an array arr[] of size N and an integer X, the task is to find the length of the longest subsequence such that the prefix sum at every element of the subsequence remains greater than zero.
Example:
Input: arr[] = {-2, -1, 1, 2, -2}, N = 5
Output: 3
Explanation: The sequence can be made of elements at index 2, 3 and 4. The prefix sum at every element stays greater than zero: 1, 3, 1Input: arr[] = {-2, 3, 3, -7, -5, 1}, N = 6
Output: 12
Â
Approach: The given problem can be solved using a greedy approach. The idea is to create a min-heap priority queue and traverse the array from the left to right. Add the current element arr[i] to the sum and minheap, and if the sum becomes less than zero, remove the most negative element from the minheap and subtract it from the sum. The below approach can be followed to solve the problem:
- Initialize a min-heap with priority queue data structure
- Initialize a variable sum to calculate the prefix sum of the desired subsequence
- Iterate the array and at every element arr[i] and add the value to the sum and min-heap
- If the value of sum becomes less than zero, remove the most negative element from the min-heap and subtract that value from the sum
- Return the size of the min-heap as the length of the longest subsequence
Below is the implementation of the above approach:
C++
// C++ implementation for the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to calculate longest length// of subsequence such that its prefix sum// at every element stays greater than zeroint maxScore(int arr[], int N){    // Variable to store the answer    int score = 0;Â
    // Min heap implementation    // using a priority queue    priority_queue<int, vector<int>,                   greater<int> >        pq;Â
    // Variable to store the sum    int sum = 0;    for (int i = 0; i < N; i++) {Â
        // Add the current element        // to the sum        sum += arr[i];Â
        // Push the element in        // the min-heap        pq.push(arr[i]);Â
        // If the sum becomes less than        // zero pop the top element of        // the min-heap and subtract it        // from the sum        if (sum < 0) {            int a = pq.top();            sum -= a;            pq.pop();        }    }Â
    // Return the answer    return pq.size();}Â
// Driver Codeint main(){Â Â Â Â int arr[] = { -2, 3, 3, -7, -5, 1 };Â Â Â Â int N = sizeof(arr) / sizeof(arr[0]);Â
    cout << maxScore(arr, N);Â
    return 0;} |
Java
// Java code for the above approachimport java.io.*;import java.util.PriorityQueue;class GFG {       // Function to calculate longest length    // of subsequence such that its prefix sum    // at every element stays greater than zero    static int maxScore(int arr[], int N)    {               // Variable to store the answer        int score = 0;Â
        // Min heap implementation        // using a priority queueÂ
        PriorityQueue<Integer> pq            = new PriorityQueue<Integer>();Â
        // Variable to store the sum        int sum = 0;        for (int i = 0; i < N; i++) {Â
            // Add the current element            // to the sum            sum += arr[i];Â
            // Push the element in            // the min-heap            pq.add(arr[i]);Â
            // If the sum becomes less than            // zero pop the top element of            // the min-heap and subtract it            // from the sum            if (sum < 0) {                int a = pq.poll();                sum -= a;            }        }Â
        // Return the answer        return pq.size();    }Â
    // Driver Code    public static void main(String[] args)    {        int arr[] = { -2, 3, 3, -7, -5, 1 };        int N = arr.length;Â
        System.out.println(maxScore(arr, N));    }}Â
// This code is contributed by Potta Lokesh |
Python3
# Python implementation for the above approachfrom queue import PriorityQueueÂ
# Function to calculate longest length# of subsequence such that its prefix sum# at every element stays greater than zerodef maxScore(arr, N):       # Variable to store the answer    score = 0;Â
    # Min heap implementation    # using a priority queue    pq = PriorityQueue();Â
    # Variable to store the sum    sum = 0;    for i in range(N) :Â
        # Add the current element        # to the sum        sum += arr[i];Â
        # Push the element in        # the min-heap        pq.put(arr[i]);Â
        # If the sum becomes less than        # zero pop the top element of        # the min-heap and subtract it        # from the sum        if (sum < 0):            a = pq.queue[0]            sum -= a;            pq.get()Â
    # Return the answer    return pq.qsize();Â
# Driver Codearr = [ -2, 3, 3, -7, -5, 1 ];N = len(arr)Â
print(maxScore(arr, N))Â
# This code is contributed by saurabh_jaiswal. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class GFG{Â
    // Function to calculate longest length    // of subsequence such that its prefix sum    // at every element stays greater than zero    static int maxScore(int []arr, int N) {Â
        // Variable to store the answer        int score = 0;Â
        // Min heap implementation        // using a priority queue        List<int> pq = new List<int>();Â
        // Variable to store the sum        int sum = 0;        for (int i = 0; i < N; i++) {Â
            // Add the current element            // to the sum            sum += arr[i];Â
            // Push the element in            // the min-heap            pq.Add(arr[i]);            pq.Sort();                       // If the sum becomes less than            // zero pop the top element of            // the min-heap and subtract it            // from the sum            if (sum < 0) {                int a = pq[0];                pq.RemoveAt(0);                sum -= a;            }        }Â
        // Return the answer        return pq.Count;    }Â
    // Driver Code    public static void Main(String[] args) {        int []arr = { -2, 3, 3, -7, -5, 1 };        int N = arr.Length;Â
        Console.WriteLine(maxScore(arr, N));    }}Â
// This code contributed by Rajput-Ji |
Javascript
<script>// javascript code for the above approachÂ
    // Function to calculate longest length    // of subsequence such that its prefix sum    // at every element stays greater than zero    function maxScore(arr , N) {Â
        // Variable to store the answer        var score = 0;Â
        // Min heap implementation        // using a priority queueÂ
        var pq = [];Â
        // Variable to store the sum        var sum = 0;        for (i = 0; i < N; i++) {Â
            // Add the current element            // to the sum            sum += arr[i];Â
            // Push the element in            // the min-heap            pq.push(arr[i]);Â
            // If the sum becomes less than            // zero pop the top element of            // the min-heap and subtract it            // from the sum            if (sum < 0) {                var a = pq.pop();                sum -= a;            }        }Â
        // Return the answer        return pq.length;    }Â
    // Driver Code        var arr = [ -2, 3, 3, -7, -5, 1 ];        var N = arr.length;Â
        document.write(maxScore(arr, N));         // This code is contributed by Rajput-Ji </script> |
Output
4
Â
 Time Complexity: O(N * log 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/length-of-longest-subsequence-such-that-prefix-sum-at-every-element-remains-greater-than-zero/ […]