Given an array arr[] consisting of N integers, the task is to find the length of the longest subsequence such that the prefix sum at each index of the subsequence is negative.
Examples:
Input: arr[] = {-1, -3, 3, -5, 8, 2}
Output: 5
Explanation: Longest subsequence satisfying the condition is {-1, -3, 3, -5, 2}.Input: arr[] = {2, -5, 2, -1, 5, 1, -9, 10}
Output: 6
Explanation: Longest subsequence satisfying the condition is {-1, -3, 3, -5, 2}.
Approach: The problem can be solved by using a Priority Queue. Follow the steps below to solve the problem:
- Initialize a priority queue, say pq, and a variable, say S as 0, to store the elements of the subsequence formed from elements up to an index i and to store the sum of the elements in the priority queue.
- Iterate over the range [0, N – 1] using the variable i and perform the following steps:
- Increment S by arr[i] and Push arr[i] into pq.
- Iterate until S is greater than 0 and in each iteration, decrement S by the top element of pq and then, pop the top element.
- Finally, after completing the above steps, print pq.size() as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum length// of a subsequence such that prefix sum// of any index is negativeint maxLengthSubsequence(int arr[], int N){ // Max priority Queue priority_queue<int> pq; // Stores the temporary sum of a // prefix of selected subsequence int S = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Increment S by arr[i] S += arr[i]; // Push arr[i] into pq pq.push(arr[i]); // Iterate until S // is greater than 0 while (S > 0) { // Decrement S by pq.top() S -= pq.top(); // Pop the top element pq.pop(); } } // Return the maxLength return pq.size();}// Driver Codeint main(){ // Given Input int arr[6] = { -1, -3, 3, -5, 8, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << maxLengthSubsequence(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.Collections;import java.util.PriorityQueue;public class GFG{ // Function to find the maximum length // of a subsequence such that prefix sum // of any index is negative static int maxLengthSubsequence(int arr[], int N) { // Max priority Queue PriorityQueue<Integer> pq = new PriorityQueue<>( Collections.reverseOrder()); // Stores the temporary sum of a // prefix of selected subsequence int S = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Increment S by arr[i] S += arr[i]; // Add arr[i] into pq pq.add(arr[i]); // Iterate until S // is greater than 0 while (S > 0) { // Decrement S by pq.peek() S -= pq.peek(); // Remove the top element pq.remove(); } } // Return the maxLength return pq.size(); } // Driver code public static void main(String[] args) { int arr[] = { -1, -3, 3, -5, 8, 2 }; int N = arr.length; // Function call System.out.println(maxLengthSubsequence(arr, N)); }}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach# Function to find the maximum length# of a subsequence such that prefix sum# of any index is negativedef maxLengthSubsequence(arr, N): # Max priority Queue pq = [] # Stores the temporary sum of a # prefix of selected subsequence S = 0 # Traverse the array arr[] for i in range(N): # Increment S by arr[i] S += arr[i] # Push arr[i] into pq pq.append(arr[i]) # Iterate until S # is greater than 0 pq.sort(reverse = False) while (S > 0): # Decrement S by pq.top() # pq.sort(reverse=False) S = S - max(pq) # Pop the top element pq = pq[1:] # print(len(pq)) # Return the maxLength return len(pq)# Driver Codeif __name__ == '__main__': # Given Input arr = [ -1, -3, 3, -5, 8, 2 ] N = len(arr) # Function call print(maxLengthSubsequence(arr, N)) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the maximum length// of a subsequence such that prefix sum// of any index is negativestatic int maxLengthSubsequence(int []arr, int N){ // Max priority Queue List<int> pq = new List<int>(); // Stores the temporary sum of a // prefix of selected subsequence int S = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Increment S by arr[i] S += arr[i]; // Push arr[i] into pq pq.Add(arr[i]); pq.Sort(); // Iterate until S // is greater than 0 while (S > 0) { pq.Sort(); // Decrement S by pq.top() S -= pq[pq.Count-1]; // Pop the top element pq.RemoveAt(0); } } // Return the maxLength return pq.Count;}// Driver Codepublic static void Main(){ // Given Input int []arr = { -1, -3, 3, -5, 8, 2 }; int N = arr.Length; // Function call Console.Write(maxLengthSubsequence(arr, N)); }}// This code is contributed by ipg2016107. |
Javascript
<script>// JavaScript program for the above approach// Function to find the maximum length// of a subsequence such that prefix sum// of any index is negativefunction maxLengthSubsequence(arr, N) { // Max priority Queue let pq = new Array(); // Stores the temporary sum of a // prefix of selected subsequence let S = 0; // Traverse the array arr[] for (let i = 0; i < N; i++) { // Increment S by arr[i] S += arr[i]; // Push arr[i] into pq pq.push(arr[i]); pq.sort((a, b) => a - b); // Iterate until S // is greater than 0 while (S > 0) { pq.sort((a, b) => a - b); // Decrement S by pq.top() S -= pq[pq.length - 1]; // Pop the top element pq.shift(); } } // Return the maxLength return pq.length;}// Driver Code// Given Inputlet arr = [-1, -3, 3, -5, 8, 2];let N = arr.length;// Function calldocument.write(maxLengthSubsequence(arr, N));// This code is contributed by gfgking</script> |
Output:
5
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!