Maximum sum possible by assigning alternate positive and negative sign to elements in a subsequence | Java program for the above approach ; Function to find the maximum sum subsequence ; Base Case ; If current state is already calculated then use it ; If current element is positive ; Update ans and recursively call with update value of flag ; Else current element is negative ; Update ans and recursively call with update value of flag ; Return maximum sum subsequence ; Function that finds the maximum sum of element of the subsequence with alternate + ve and - ve signs ; Create auxiliary array dp [ ] [ ] ; Initialize dp [ ] [ ] ; Function Call ; Driver Code ; Given array arr [ ] ; Function call
import java . io . * ; import java . util . Arrays ; class GFG { static int findMax ( int [ ] a , int dp [ ] [ ] , int i , int flag ) { if ( i == ( int ) a . length ) { return 0 ; } if ( dp [ i ] [ flag ] != - 1 ) { return dp [ i ] [ flag ] ; } int ans ; if ( flag == 0 ) { ans = Math . max ( findMax ( a , dp , i + 1 , 0 ) , a [ i ] + findMax ( a , dp , i + 1 , 1 ) ) ; } else { ans = Math . max ( findMax ( a , dp , i + 1 , 1 ) , - 1 * a [ i ] + findMax ( a , dp , i + 1 , 0 ) ) ; } return dp [ i ] [ flag ] = ans ; } static void findMaxSumUtil ( int [ ] arr , int N ) { int dp [ ] [ ] = new int [ N ] [ 2 ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < 2 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } System . out . println ( findMax ( arr , dp , 0 , 0 ) ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 3 , 4 , 1 , 2 } ; int N = arr . length ; findMaxSumUtil ( arr , N ) ; } }