Maximum sum possible by assigning alternate positive and negative sign to elements in a subsequence | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMax ( vector < int > & a , int dp [ ] [ 2 ] , int i , int flag ) { if ( i == ( int ) a . size ( ) ) { return 0 ; } if ( dp [ i ] [ flag ] != -1 ) { return dp [ i ] [ flag ] ; } int ans ; if ( flag == 0 ) { ans = max ( findMax ( a , dp , i + 1 , 0 ) , a [ i ] + findMax ( a , dp , i + 1 , 1 ) ) ; } else { ans = max ( findMax ( a , dp , i + 1 , 1 ) , -1 * a [ i ] + findMax ( a , dp , i + 1 , 0 ) ) ; } return dp [ i ] [ flag ] = ans ; } void findMaxSumUtil ( vector < int > & arr , int N ) { int dp [ N ] [ 2 ] ; memset ( dp , -1 , sizeof dp ) ; cout << findMax ( arr , dp , 0 , 0 ) ; } int main ( ) { vector < int > arr = { 1 , 2 , 3 , 4 , 1 , 2 } ; int N = arr . size ( ) ; findMaxSumUtil ( arr , N ) ; return 0 ; }