Longest subsequence with non negative prefix sum at each position | Function to find the length of the longest subsequence with non negative prefix sum at each position ; 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
function longestSubsequence ( arr , N ) { let dp = Array ( N ) . fill ( ) . map ( ( ) => Array ( N + 1 ) . fill ( - 1 ) ) ; for ( let i = 0 ; i < N ; ++ i ) { dp [ i ] [ 0 ] = 0 ; } dp [ 0 ] [ 1 ] = ( arr [ 0 ] >= 0 ? arr [ 0 ] : - 1 ) ; for ( let i = 1 ; i < N ; ++ i ) { for ( let j = 1 ; j <= ( i + 1 ) ; ++ j ) { if ( dp [ i - 1 ] [ j ] != - 1 ) { dp [ i ] [ j ] = Math . 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 ] = Math . max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j - 1 ] + arr [ i ] ) ; } } } let ans = 0 ; for ( let j = 0 ; j <= N ; ++ j ) { if ( dp [ N - 1 ] [ j ] >= 0 ) { ans = j ; } } document . write ( ans ) ; } let arr = [ 4 , - 4 , 1 , - 3 , 1 , - 3 ] ; let N = arr . length ; longestSubsequence ( arr , N ) ;