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

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

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.

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!

Live masterclass