Longest subsequence with non negative prefix sum at each position | C ++ program for the above approach ; Function to find the length of the longest subsequence with non negative prefix sum at each position ; Stores the maximum sum possible if we include j elements till the position i ; Initialize dp array with - 1 ; Maximum subsequence sum by including no elements till position ' i ' ; Maximum subsequence sum by including first element at first position ; Iterate over all the remaining positions ; If the current element is excluded ; If current element is included and if total sum is positive or not ; Select the maximum j by which a non negative prefix sum subsequence can be obtained ; Print the answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void longestSubsequence ( int * arr , int N ) { int dp [ N ] [ N + 1 ] ; memset ( dp , -1 , sizeof dp ) ; for ( int i = 0 ; i < N ; ++ i ) { dp [ i ] [ 0 ] = 0 ; } dp [ 0 ] [ 1 ] = ( arr [ 0 ] >= 0 ? arr [ 0 ] : -1 ) ; for ( int i = 1 ; i < N ; ++ i ) { for ( int j = 1 ; j <= ( i + 1 ) ; ++ j ) { if ( dp [ i - 1 ] [ j ] != -1 ) { dp [ i ] [ j ] = max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j ] ) ; } 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 ; for ( int j = 0 ; j <= N ; ++ j ) { if ( dp [ N - 1 ] [ j ] >= 0 ) { ans = j ; } } cout << ans << endl ; } int main ( ) { int arr [ ] = { 4 , -4 , 1 , -3 , 1 , -3 } ; int N = sizeof arr / sizeof arr [ 0 ] ; longestSubsequence ( arr , N ) ; return 0 ; }