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
def longestSubsequence ( arr , N ) : NEW_LINE INDENT dp = [ [ - 1 for i in range ( N + 1 ) ] for i in range ( N ) ] NEW_LINE DEDENT ' NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 0 NEW_LINE DEDENT dp [ 0 ] [ 1 ] = arr [ 0 ] if arr [ 0 ] >= 0 else - 1 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( 1 , i + 2 ) : NEW_LINE INDENT if ( dp [ i - 1 ] [ j ] != - 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j ] ) NEW_LINE DEDENT if ( dp [ i - 1 ] [ j - 1 ] >= 0 and dp [ i - 1 ] [ j - 1 ] + arr [ i ] >= 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j - 1 ] + arr [ i ] ) NEW_LINE DEDENT DEDENT DEDENT ans = 0 NEW_LINE for j in range ( N + 1 ) : NEW_LINE INDENT if ( dp [ N - 1 ] [ j ] >= 0 ) : NEW_LINE INDENT ans = j NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT arr = [ 4 , - 4 , 1 , - 3 , 1 , - 3 ] NEW_LINE N = len ( arr ) NEW_LINE longestSubsequence ( arr , N ) NEW_LINE