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
using System ; class GFG { static void longestSubsequence ( int [ ] arr , int N ) { int [ , ] dp = new int [ N , N + 1 ] ; for ( int i = 0 ; i < N ; ++ i ) { for ( int j = 0 ; j < N + 1 ; ++ j ) { dp [ i , j ] = - 1 ; } } 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 ] = 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 ] ) ; } } } int ans = 0 ; for ( int j = 0 ; j <= N ; ++ j ) { if ( dp [ N - 1 , j ] >= 0 ) { ans = j ; } } Console . Write ( ans ) ; } public static void Main ( ) { int [ ] arr = { 4 , - 4 , 1 , - 3 , 1 , - 3 } ; int N = arr . Length ; longestSubsequence ( arr , N ) ; } }