Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Approaches
4.
Code
5.
Code
6.
Complexity analysis
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Malay Gain
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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

  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!

 

 

Previous article
House Robber 2
Next article
Minimum Number of Days in which No Task is Performed
Live masterclass