A subsequence of an array means a sequence of some array elements omitting some elements but maintaining their order as in the given array.

For example, {4,7,8} is a subsequence of arr[ ]={4,3,7,1,8}; but {7,4,8} not as the relative order of array elements is changed. Here we will see how to find the maximum subsequence sum among all possible subsequences after putting alternative positive and negative signs in each subsequence.

Problem statement

You are given an array of integers. Find the maximum subsequence sum of among all possible subsequences after putting positive and negative signs alternatively in each subsequence.

Input

arr[ ]={4,5, 2, 3}

Output

Max subsequnce sum = 6

Explanation

Note: Please try to solve the problem first and then see the below solution approach.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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));
}
}

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);
}

Output

max subsequence sum with alternating sign : 6

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

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.

What are the main two techniques used in DP? These are tabulation and memorization.

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.

We highly encourage you to use Coding Ninjas Studiofor 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.