Given an array arr[] consisting of N integers, the task is to find the longest subsequence such that the prefix sum at each position of the subsequence is non-negative.
Examples:
Input: arr[] = {4, -4, 1, -3, 1, -3}
Output: 5
Explanation:
Consider the subsequence as {4, 1, -3, 1, -3}. Now, the prefix sum of the chosen subsequence is {4, 5, 2, 3, 0}. Since, the prefix sum is non-negative at every possible index. Therefore, this subsequence is of maximum length having length 5.Input: arr[] = {1, 3, 5, 7}
Output: 4
Naive Approach: The simplest approach to solve this problem is to generate all possible subsequences of the given array and print the length of that subsequence that has a non-negative prefix sum at each position and is of maximum length.
Time Complexity: O(2N)
Auxiliary Space: O(2N)
Efficient Approach: The above approach can also be optimized by using Dynamic Programming because it has Overlapping Subproblems property and Optimal Substructure property. Like other Dynamic Programming(DP) problems, recomputation of the same subproblems can be avoided by constructing a temporary array that stores the results of subproblems. Follow the steps below to solve the problem:
- Initialize a matrix, say dp[][] where dp[i][j] stores the maximum sum possible if there are j valid elements till position i and initializing dp[][] array with -1.
- Iterate over the range [0, N – 1] using the variable i and update dp[i][0] as 0.
- If the value of arr[0] is at least 0, then update dp[0][1] as arr[0]. Otherwise, update it as -1.
- Iterate over the range [1, N – 1] using the variable i:
- Iterate over the range [1, i + 1] using the variable j:
- If current element is excluded i.e., if dp[i – 1][j] is not equal to -1, then update dp[i][j] as max of dp[i][j] and dp[i – 1][j].
- If current element is included i.e., if dp[i – 1][j – 1] and dp[i – 1][j – 1] + arr[i] are greater than equal to 0, then update the value of dp[i][j] as the maximum of dp[i][j] and dp[i – 1][j – 1] + arr[i].
- Iterate over the range [1, i + 1] using the variable j:
- Initialize a variable say, ans as 0 to store the longest subsequence with non-negative prefix sum at each position.
- Iterate in the range [0, N] using the variable j and if dp[N – 1][j] is greater than equal to 0, then update the value of ans as j.
- After completing the above steps, print the value of ans as the result.
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 length of the// longest subsequence with non negative// prefix sum at each positionvoid longestSubsequence(int* arr, int N){ // Stores the maximum sum possible // if we include j elements till // the position i int dp[N][N + 1]; // Initialize dp array with -1 memset(dp, -1, sizeof dp); // Maximum subsequence sum by // including no elements till // position 'i' for (int i = 0; i < N; ++i) { dp[i][0] = 0; } // Maximum subsequence sum by // including first element at // first position dp[0][1] = (arr[0] >= 0 ? arr[0] : -1); // Iterate over all the remaining // positions for (int i = 1; i < N; ++i) { for (int j = 1; j <= (i + 1); ++j) { // If the current element // is excluded if (dp[i - 1][j] != -1) { dp[i][j] = max( dp[i][j], dp[i - 1][j]); } // If current element is // included and if total // sum is positive or not if (dp[i - 1][j - 1] >= 0 && dp[i - 1][j - 1] + arr[i] >= 0) { dp[i][j] = max( dp[i][j], dp[i - 1][j - 1] + arr[i]); } } } int ans = 0; // Select the maximum j by which // a non negative prefix sum // subsequence can be obtained for (int j = 0; j <= N; ++j) { if (dp[N - 1][j] >= 0) { ans = j; } } // Print the answer cout << ans << endl;}// Driver Codeint main(){ int arr[] = { 4, -4, 1, -3, 1, -3 }; int N = sizeof arr / sizeof arr[0]; longestSubsequence(arr, N); return 0;} |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class GFG{// Function to find the length of the// longest subsequence with non negative// prefix sum at each positionstatic void longestSubsequence(int[] arr, int N){ // Stores the maximum sum possible // if we include j elements till // the position i int dp[][] = new int[N][N + 1]; // Initialize dp array with -1 for(int i = 0; i < N; ++i) { for(int j = 0; j < N + 1; ++j) { dp[i][j] = -1; } } // Maximum subsequence sum by // including no elements till // position 'i' for(int i = 0; i < N; ++i) { dp[i][0] = 0; } // Maximum subsequence sum by // including first element at // first position dp[0][1] = (arr[0] >= 0 ? arr[0] : -1); // Iterate over all the remaining // positions for(int i = 1; i < N; ++i) { for(int j = 1; j <= (i + 1); ++j) { // If the current element // is excluded if (dp[i - 1][j] != -1) { dp[i][j] = Math.max( dp[i][j], dp[i - 1][j]); } // If current element is // included and if total // sum is positive or not if (dp[i - 1][j - 1] >= 0 && dp[i - 1][j - 1] + arr[i] >= 0) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + arr[i]); } } } int ans = 0; // Select the maximum j by which // a non negative prefix sum // subsequence can be obtained for(int j = 0; j <= N; ++j) { if (dp[N - 1][j] >= 0) { ans = j; } } // Print the answer System.out.println(ans);}// Driver codepublic static void main(String[] args){ int arr[] = { 4, -4, 1, -3, 1, -3 }; int N = arr.length; longestSubsequence(arr, N);}}// This code is contributed by avijitmondal1998 |
Python3
# Python3 Program for the above approach# Function to find the length of the# longest subsequence with non negative# prefix sum at each positiondef longestSubsequence(arr, N): # Stores the maximum sum possible # if we include j elements till # the position i # Initialize dp array with -1 dp = [[-1 for i in range(N + 1)] for i in range(N)] # Maximum subsequence sum by # including no elements till # position 'i' for i in range(N): dp[i][0] = 0 # Maximum subsequence sum by # including first element at # first position dp[0][1] = arr[0] if arr[0] >= 0 else -1 # Iterate over all the remaining # positions for i in range(1, N): for j in range(1, i + 2): # If the current element # is excluded if (dp[i - 1][j] != -1): dp[i][j] = max(dp[i][j], dp[i - 1][j]) # If current element is # included and if total # sum is positive or not if (dp[i - 1][j - 1] >= 0 and dp[i - 1][j - 1] + arr[i] >= 0): dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + arr[i]) ans = 0 # Select the maximum j by which # a non negative prefix sum # subsequence can be obtained for j in range(N + 1): if (dp[N - 1][j] >= 0): ans = j # Print the answer print(ans)# Driver Codearr = [4, -4, 1, -3, 1, -3]N = len(arr)longestSubsequence(arr, N)# This code is contributed by _saurabhy_jaiswal |
C#
// C# program for the above approachusing System;class GFG{// Function to find the length of the// longest subsequence with non negative// prefix sum at each positionstatic void longestSubsequence(int[] arr, int N){ // Stores the maximum sum possible // if we include j elements till // the position i int[,] dp = new int[N, N + 1]; // Initialize dp array with -1 for(int i = 0; i < N; ++i) { for(int j = 0; j < N + 1; ++j) { dp[i, j] = -1; } } // Maximum subsequence sum by // including no elements till // position 'i' for(int i = 0; i < N; ++i) { dp[i, 0] = 0; } // Maximum subsequence sum by // including first element at // first position dp[0, 1] = (arr[0] >= 0 ? arr[0] : -1); // Iterate over all the remaining // positions for(int i = 1; i < N; ++i) { for(int j = 1; j <= (i + 1); ++j) { // If the current element // is excluded if (dp[i - 1, j] != -1) { dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j]); } // If current element is // included and if total // sum is positive or not if (dp[i - 1, j - 1] >= 0 && dp[i - 1, j - 1] + arr[i] >= 0) { dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j - 1] + arr[i]); } } } int ans = 0; // Select the maximum j by which // a non negative prefix sum // subsequence can be obtained for(int j = 0; j <= N; ++j) { if (dp[N - 1, j] >= 0) { ans = j; } } // Print the answer Console.Write(ans);}// Driver codepublic static void Main(){ int[] arr = { 4, -4, 1, -3, 1, -3 }; int N = arr.Length; longestSubsequence(arr, N);}}// This code is contributed by ukasp |
Javascript
<script> // JavaScript Program for the above approach // Function to find the length of the // longest subsequence with non negative // prefix sum at each position function longestSubsequence(arr, N) { // Stores the maximum sum possible // if we include j elements till // the position i // Initialize dp array with -1 let dp = Array(N).fill().map(() => Array(N + 1).fill(-1)); // Maximum subsequence sum by // including no elements till // position 'i' for (let i = 0; i < N; ++i) { dp[i][0] = 0; } // Maximum subsequence sum by // including first element at // first position dp[0][1] = (arr[0] >= 0 ? arr[0] : -1); // Iterate over all the remaining // positions for (let i = 1; i < N; ++i) { for (let j = 1; j <= (i + 1); ++j) { // If the current element // is excluded if (dp[i - 1][j] != -1) { dp[i][j] = Math.max( dp[i][j], dp[i - 1][j]); } // If current element is // included and if total // sum is positive or not if (dp[i - 1][j - 1] >= 0 && dp[i - 1][j - 1] + arr[i] >= 0) { dp[i][j] = Math.max( dp[i][j], dp[i - 1][j - 1] + arr[i]); } } } let ans = 0; // Select the maximum j by which // a non negative prefix sum // subsequence can be obtained for (let j = 0; j <= N; ++j) { if (dp[N - 1][j] >= 0) { ans = j; } } // Print the answer document.write(ans); } // Driver Code let arr = [4, -4, 1, -3, 1, -3]; let N = arr.length; longestSubsequence(arr, N); // This code is contributed by Potta Lokesh </script> |
Output
5
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size N+1.
- Set a base case by initializing the values of DP .
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Initialize a variable ans to store the final answer and update it by iterating through the Dp.
- At last return and print the final answer stored in ans .
Implementation:
C++
#include <bits/stdc++.h>using namespace std;// This function finds the length of the longest subsequence// with a non-negative prefix sum at each positionvoid longestSubsequence(int* arr, int N){ // Initialize an array to store the maximum subsequence sum // with j elements till the position i int dp[N + 1]; // Initialize the dp array with -1 memset(dp, -1, sizeof dp); // Maximum subsequence sum with no elements till position i is 0 dp[0] = 0; // Maximum subsequence sum with first element at first position dp[1] = (arr[0] >= 0 ? arr[0] : -1); // Iterate over all the remaining positions for (int i = 1; i < N; ++i) { // Iterate over all the possible j values // (from 1 to i+1 or N, whichever is smaller) for (int j = min(i + 1, N); j >= 1; --j) { // If the current element is excluded if (dp[j] != -1) { dp[j] = max(dp[j], dp[j - 1] + arr[i]); } // If the current element is included and the total // sum is positive or zero if (dp[j - 1] >= 0 && dp[j - 1] + arr[i] >= 0) { dp[j] = max(dp[j], dp[j - 1] + arr[i]); } } } // Find the maximum j value for which a non-negative prefix // sum subsequence can be obtained int ans = 0; for (int j = 0; j <= N; ++j) { if (dp[j] >= 0) { ans = j; } } // Print the answer cout << ans << endl;}// Driver code to test the functionint main(){ int arr[] = { 4, -4, 1, -3, 1, -3 }; int N = sizeof arr / sizeof arr[0]; longestSubsequence(arr, N); return 0;} |
Java
import java.util.Arrays;public class Main { // This function finds the length of the longest subsequence // with a non-negative prefix sum at each position public static void longestSubsequence(int[] arr, int N) { // Initialize an array to store the maximum subsequence sum // with j elements till the position i int[] dp = new int[N + 1]; // Initialize the dp array with -1 Arrays.fill(dp, -1); // Maximum subsequence sum with no elements till position i is 0 dp[0] = 0; // Maximum subsequence sum with first element at first position dp[1] = (arr[0] >= 0 ? arr[0] : -1); // Iterate over all the remaining positions for (int i = 1; i < N; ++i) { // Iterate over all the possible j values // (from 1 to i+1 or N, whichever is smaller) for (int j = Math.min(i + 1, N); j >= 1; --j) { // If the current element is excluded if (dp[j] != -1) { dp[j] = Math.max(dp[j], dp[j - 1] + arr[i]); } // If the current element is included and the total // sum is positive or zero if (dp[j - 1] >= 0 && dp[j - 1] + arr[i] >= 0) { dp[j] = Math.max(dp[j], dp[j - 1] + arr[i]); } } } // Find the maximum j value for which a non-negative prefix // sum subsequence can be obtained int ans = 0; for (int j = 0; j <= N; ++j) { if (dp[j] >= 0) { ans = j; } } // Print the answer System.out.println(ans); } // Driver code to test the function public static void main(String[] args) { int[] arr = {4, -4, 1, -3, 1, -3}; int N = arr.length; longestSubsequence(arr, N); }} |
Python
def longestSubsequence(arr, N): # Initialize an array to store the maximum subsequence sum # with j elements till the position i dp = [-1] * (N + 1) # Maximum subsequence sum with no elements till position i is 0 dp[0] = 0 # Maximum subsequence sum with first element at first position dp[1] = arr[0] if arr[0] >= 0 else -1 # Iterate over all the remaining positions for i in range(1, N): # Iterate over all the possible j values # (from 1 to i+1 or N, whichever is smaller) for j in range(min(i + 1, N), 0, -1): # If the current element is excluded if dp[j] != -1: dp[j] = max(dp[j], dp[j - 1] + arr[i]) # If the current element is included and the total # sum is positive or zero if dp[j - 1] >= 0 and dp[j - 1] + arr[i] >= 0: dp[j] = max(dp[j], dp[j - 1] + arr[i]) # Find the maximum j value for which a non-negative prefix # sum subsequence can be obtained ans = 0 for j in range(N + 1): if dp[j] >= 0: ans = j # Print the answer print(ans)# Driver code to test the functionif __name__ == '__main__': arr = [4, -4, 1, -3, 1, -3] N = len(arr) longestSubsequence(arr, N) |
C#
using System;class GFG{ // This function finds the length of the longest subsequence // with a non-negative prefix sum at each position static void longestSubsequence(int[] arr, int N) { // Initialize an array to store the maximum subsequence sum // with j elements till the position i int[] dp = new int[N + 1]; // Initialize the dp array with -1 Array.Fill(dp, -1); // Maximum subsequence sum with no elements till position i is 0 dp[0] = 0; // Maximum subsequence sum with first element at first position dp[1] = (arr[0] >= 0 ? arr[0] : -1); // Iterate over all the remaining positions for (int i = 1; i < N; ++i) { // Iterate over all the possible j values // (from 1 to i+1 or N, whichever is smaller) for (int j = Math.Min(i + 1, N); j >= 1; --j) { // If the current element is excluded if (dp[j] != -1) { dp[j] = Math.Max(dp[j], dp[j - 1] + arr[i]); } // If the current element is included and the total // sum is positive or zero if (dp[j - 1] >= 0 && dp[j - 1] + arr[i] >= 0) { dp[j] = Math.Max(dp[j], dp[j - 1] + arr[i]); } } } // Find the maximum j value for which a non-negative prefix // sum subsequence can be obtained int ans = 0; for (int j = 0; j <= N; ++j) { if (dp[j] >= 0) { ans = j; } } // Print the answer Console.WriteLine(ans); } // Driver code to test the function static void Main(string[] args) { int[] arr = { 4, -4, 1, -3, 1, -3 }; int N = arr.Length; longestSubsequence(arr, N); }} |
Javascript
// This function finds the length of the longest subsequence// with a non-negative prefix sum at each positionfunction longestSubsequence(arr, N) { // Initialize an array to store the maximum subsequence sum // with j elements till the position i // Initialize the dp array with -1 let dp = new Array(N + 1).fill(-1); // Maximum subsequence sum with no elements till position i is 0 dp[0] = 0; // Maximum subsequence sum with first element at first position dp[1] = arr[0] >= 0 ? arr[0] : -1; // Iterate over all the remaining positions for (let i = 1; i < N; ++i) { // Iterate over all the possible j values // (from 1 to i+1 or N, whichever is smaller) for (let j = Math.min(i + 1, N); j >= 1; --j) { // If the current element is excluded if (dp[j] !== -1) { dp[j] = Math.max(dp[j], dp[j - 1] + arr[i]); } // If the current element is included and the total // sum is positive or zero if (dp[j - 1] >= 0 && dp[j - 1] + arr[i] >= 0) { dp[j] = Math.max(dp[j], dp[j - 1] + arr[i]); } } } // Find the maximum j value for which a non-negative prefix // sum subsequence can be obtained let ans = 0; for (let j = 0; j <= N; ++j) { if (dp[j] >= 0) { ans = j; } } // Print the answer console.log(ans);}// Test caselet arr = [4, -4, 1, -3, 1, -3];let N = arr.length;longestSubsequence(arr, N); |
Output:
5
Time Complexity: O(N^2)
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!
