# Length of longest subsequence such that prefix sum at every element remains greater than zero

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {-2, -1, 1, 2, -2}, N = 5Output:3Explanation: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, 1

Input:arr[] = {-2, 3, 3, -7, -5, 1}, N = 6Output: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 zero` `int` `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 Code` `int` `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 approach` `import` `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` |

**Output**

4

**Time Complexity: **O(N * log N)**Auxiliary Space: **O(N)