1.
Introduction
2.
Problem Statement
2.1.
Test Cases
3.
Approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.3.
Complexity Analysis
3.3.1.
Dry Run of test cases
4.
4.1.
What is Min Heap data structure?
4.2.
What is meant by the subsequence of an array?
4.3.
Is the longest subsequence the same as the longest subarray for a given array?
4.4.
In which type of problems should we use Heap?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Length of Longest Subsequence such that Prefix Sum at Every Element Remains Greater than Zero

Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## Introduction

This problem is based on finding the longest subsequence such that the prefix sum at every element remains greater than zero. Min Heap, which is a very popular and important data structure, is used in the solution. This blog will help you to strengthen your conceptual foundation of Min Heap data structure.

Also see, Implementation of Heap

## Problem Statement

Given an array of elements, find out the length of the longest subsequence such that the prefix sum at every element remains greater than zero.

### Test Cases

Let us take two test cases to understand the problem better,

Test Case 1:

For this given array, the output is 4.

Test Case 2:

For this given array, the output is 3.

NOTE: In this problem, we have to find the length of the longest subsequence, not the longest subarray. Subsequence refers to a non-contiguous sequence of a given sequence, obtained by deleting one or more elements from the original sequence.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Approach

To solve this problem, we will use the Min Heap data structure. We will go through each element of the array and push it in the Min Heap. We will also add the element to the sum variable, which will keep track of the prefix sum of the current element.

If the prefix sum becomes negative, we subtract the most negative element from the heap and pop that element from the heap.

As it is a Min Heap, the most negative element will be present at the top of the heap. We are using Min Heap in this solution as it is very easy and quick to access the minimum element from any current step.

### Steps of Algorithm

1. Take input of vectors from the user.
2. Create an empty Min Heap using Priority Queue.
3. Initialize the sum variable as 0.
4. Run a for loop from 0 to n(size of vector)
5. Add the value of the current element of the vector to the sum
6. Add the current element of the vector to the Min Heap
7. Check if the sum has become negative
• If the sum is negative
• Subtract the most negative/top element from the sum
• Pop the top element from the Min Heap
8. Else
• Continue

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> vec, int n)
{
priority_queue<int, vector<int>, greater<int>> min_heap; //Creating the Min Heap
int sum = 0;                                             //Initializing sum as 0
for (int i = 0; i < n; i++)
{
sum += vec[i];         //Adding current element's value to sum
min_heap.push(vec[i]); //Pushing current element to heap
if (sum < 0)           //If sum becomes negative
{
int a = min_heap.top();
sum -= a;       //Subtract top element's value from sum
min_heap.pop(); //Pop the top element from heap
}
}
return min_heap.size(); //return the ans
}
int main()
{
vector<int> vec;
int n, x;
cout << "Enter the size of the array:" << endl;
cin >> n;
cout << "Enter the elements:" << endl;
for (int i = 0; i < n; i++)
{
cin >> x;
vec.push_back(x);
}
cout << "Length of the longest subsequence is: " << solve(vec, n);
return 0;
}``````

Input:

``````Enter the size of the array:
6
Enter the elements:
-1 6 7 -15 -3 -1``````

Output:

``Length of the longest subsequence is: 4``

### Complexity Analysis

Time Complexity

O(n*logn) as we are traversing through a for loop â€˜nâ€™ number of times. The push and pop operations of priority queue take O(logn) time, making the overall time complexity O(n*logn).  Here, n refers to the number of elements in the input vector.

Space Complexity

O(n), as we are using a priority queue of size n. Here, n refers to the number of elements in the input vector.

#### Dry Run of test cases

Letâ€™s look at the dry run of Test Case 1 to understand the problem better.

The input array is,

-1, 6, 7, -15, -3, -1

Initially, sum = 0, and the Min Heap is also empty.

-1 is inserted to the Min Heap, and sum = -1.

But, as the sum becomes negative, we pop the top element from the Heap.

The next element, i.e., 6 is inserted in a heap, and the new sum becomes 6.

We then go to the next element of the vector, i.e., 7. The current sum becomes 13 (6+7). Hence, 7 is also inserted into the heap.

The next element is -15, and adding it makes the sum negative.

The sum becomes -2, so we again pop the top element of the heap, i.e., -15.

We also deduct -15 from our sum, making sum = 13.

The next element in the vector is -3; adding it to our sum makes it 10, which is a positive number. So, it is also added to the Heap.

We finally reach the last element of the vector, i.e., -1, and we add it to the current sum. It is also pushed into the Heap.

So our current sum is 9, and our Min Heap will look like this,

In the end, the size of our Min Heap is 4, indicating the length of the longest subsequence.

### What is Min Heap data structure?

Min Heap is a binary tree, where the root node of the tree has a value less than its children. Like the root node, the other internal nodes also need to have a smaller value than their respective children.

### What is meant by the subsequence of an array?

Subsequence refers to a non-contiguous sequence of a given array, obtained by deleting one or more elements from the original array.

### Is the longest subsequence the same as the longest subarray for a given array?

No, they are not the same. Longest subsequent refers to the longest possible non-contiguous sequence for a given array, but subarray refers to the longest possible contiguous section.

### In which type of problems should we use Heap?

In problems where you have to find the minimum element (Min Heap) and maximum(Max Heap) element from a list of elements very quickly, Heap should be used.

## Conclusion

In this blog, we saw how to solve the given problem using the Min Heap data structure.

We hope you completely understand the solution, but if you are new to Min Heap, we suggest you go through this blog to understand the critical concepts related to it.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy learning, Ninja!

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems