Maximize Subsequence Sum after a Plus-Minus Sign Alternatively on Elements

Approaches

As it is one kind of maximization problem, it can be solved dynamic programming-based approach. In the native recursive approach, this problem can also be solved. But using the memoization technique of dynamic programming it can be optimized. 

Recursive approach

• For generating all possible subsequences we can choose an element from the array or skip it. 
• When the current index will become equal to the size of the array, the recursive function will terminate.
• But to add a sign before each element of a subsequence, we need to keep track of the current subsequence size, curr_size.
• If cur_size is even, then we will add the next element with the +ve sign or skip it.
•  If cur_size is odd, add the next element with a -ve sign or skip it.

Code

int maxSum(int i,int curr_size,vector<int>& nums)    {    //when current index exceeds the array        if(i>=nums.size())            return 0;                            //if current size of subsequence is even, add the next element with +ve sign or skip it        if(curr_size%2==0)        {            return max(maxSum(i+1,curr_size+1,nums)+nums[i],maxSum(i+1,curr_size,nums));        }        //if current size of subsequence is odd, add the next element with -ve sign or skip it        else        {           return max(maxSum(i+1,curr_size+1,nums)-nums[i],maxSum(i+1,curr_size,nums));        }    }    You can also try this code with Online C++ Compiler Run Code

DP approach(using memoization)

From the above approach, we can easily observe the state of the recursive call that depends on the current index and the current size of the subsequence. As this problem has overlapping subproblem and optimal substructure(maximization) property, we can use 2D array dp[ ][ ] to store the calculated value of corresponding recursive states to avoid recomputation of same states again and again.

This memoization technique reduces exponential time complexity to linear time complexity.

Code

// C++ implementation of memoization technique //for finding max subsequence sum with alternating sign #include<bits/stdc++.h> using namespace std; vector<vector<int>>dp;          int maxSum(int i,int curr_size,vector<int>& nums) { //when current index exceeds the array    if(i>=nums.size())        return 0;       //if value of current dp state is pre-calculated    if(dp[i][curr_size%2]!=-1)        return dp[i][curr_size%2];       //if current size of subsequence is even, add the next element with +ve sign or skip it    if(curr_size%2==0)    {        return dp[i][curr_size%2]=max(maxSum(i+1,curr_size+1,nums)+nums[i],maxSum(i+1,curr_size,nums));    }    //if current size of subsequence is odd, add the next element with -ve sign or skip it    else    {       return dp[i][curr_size%2]= max(maxSum(i+1,curr_size+1,nums)-nums[i],maxSum(i+1,curr_size,nums));    } } //driver code int main() { vector<int> arr{4,5,2,3}; dp.resize(arr.size(),vector<int>(2,-1)); cout<<"max subsequence sum with alternating sign : "<<maxSum(0,0,arr); } You can also try this code with Online C++ Compiler Run Code

Output

Complexity analysis

The time complexity of the dynamic programming-based approach is O(n) where n is the size of the given array.

 As we are using a 2D array of size (n*2), space complexity is also O(n).

FAQs

1. What is Dynamic programming?
   Dynamic Programming is a technique of optimizing over recursion by storing the answer for the overlapping subproblems and using that result for the same problem in the future. So, it saves the time of re-computing the answer for the same problem and helps to reduce the exponential time complexity to polynomial time complexity.
    
2. What are the main two techniques used in DP?
   These are tabulation and memorization.
    
3. What are the main properties of DP problems?
   Overlapping subproblem and optimal substructure.

Key Takeaways

This article covered how to maximize subsequence sum after putting plus-minus sign alternatively on an element along with C++ implementation of solution approaches.

We highly recommend going through the articles on dynamic programming to grasp the concepts clearly.

Check out this problem - Count Ways To Reach The Nth Stair 

We highly encourage you to use Coding Ninjas Studio for practising various Data structures, and algorithm questions typically asked in coding interviews. It will definitely help you in mastering efficient coding techniques and cracking your dream jobs. 

Happy learning!