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.
Approach: Dynamic Programming
3.1.
Code
3.2.
Complexity Analysis
3.2.1.
Time Complexity: O(N)
3.2.2.
Space Complexity: O(N)
4.
Frequently Asked Questions
5.
Key Takeaways
Last Updated: Mar 27, 2024

Maximise Difference Between Sum Of Even And Odd-Indexed Elements Of A Subsequence

Author Rhythm Jain
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The given problem is based on dynamic programming. At first, the problem may seem confusing, but it is a piece of cake as soon as you realize the constraints.

Problem Statement

We have an array arr[] consisting of N positive integers. Our task is to find the maximum value of the difference between the sum of elements at even and odd places for any subsequence of the array arr[].

Example:

Input:

[1, 2, 3, 4, 5, 6]

Output:

6

Explanation:

Considering the subsequence that contains only [6], we have a  sum at even places = 0 and odd places = 6. So it gives us a difference of 6, which is the maximum.

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

Approach: Dynamic Programming

One obvious approach is to produce all the possible subsequences of the given array and maximize the difference between the sum of items at even and odd indices for each subsequence. But that would be very inefficient, both in time complexity and space complexity.

If we observe, we have two cases to consider whether the subsequence length is odd or even. Therefore, we would require two arrays, dp1[] and dp2[], each of size equal to the size of the given array.

dp1[i] will store the maximum difference between the sum of odd and even numbers up to index i such that subsequence length is odd.

dp2[i] will store the maximum difference between the sum of odd and even numbers up to index i such that subsequence length is even.

Suppose the length of the given array is N.

Algorithm:

  • As mentioned above, create two arrays, dp1[] and dp2[], of length N and initialize them with value -1.
  • Set dp1[0]=arr[0] and dp2[0]=0.
  • Iterate from 1 to N, and at each iteration
    • Set dp1[i] = max( dp1[i-1], dp2[i-1] + arr[i]). This is because the ith element will be added to the even length subsequence in order to make it an odd length sequence.
    • Set dp2[i] = max( dp2[i-1], dp1[i-1] - arr[i] ). This is because the ith element will be subtracted from the odd length subsequence in order to make it an even length subsequence.
  • Return maximum of dp1[N-1] and dp2[N-1].

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int findMaximumDiff(vector<int> arr)
{
    int n=arr.size();
	// Initialize the two arrays
	vector<int> dp1(n,-1),dp2(n,-1);
	dp2[0] = 0;
	dp1[0] = arr[0];

	// Iterate over the range
	for (int i = 1; i < n; i++) {
		dp1[i] = max(dp1[i - 1],dp2[i - 1] + arr[i]);
		dp2[i] = max(dp2[i - 1],dp1[i - 1] - arr[i]);
	}
    
	return max(dp1[n - 1], dp2[n - 1]);
}

// Driver Code
int main()
{
	vector<int> arr= { 1,2,3,4,5,6 };
	cout<<findMaximumDiff(arr);
	return 0;
}

Output:

6

Complexity Analysis

Time Complexity: O(N)

Because we'll have to go through the entire array.

Space Complexity: O(N)

We need two auxiliary arrays to keep track of the maximum sum difference for each index.

Frequently Asked Questions

  1. What is a subsequence?
    A subsequence of a given sequence is a sequence that may be formed from the provided sequence by removing some or all of the components while keeping the remaining elements in the same order.
     
  2. How to convert the recursive solution to a dynamic approach-based solution?
    If we have repeated subproblems in the recursive solution, that solution can be further optimized by applying memoization. The memoization-based solution can be further converted to a dynamic programming approach. For more insights about memoization and dynamic programming, you can visit here.
     
  3. What do you mean by Dynamic Programming?
    Dynamic Programming or DP is a specialized algorithm paradigm in computer science. This technique solves an optimization problem by breaking it down into simpler subproblems. We do so by keeping in mind that the optimal solution to the overall problem depends on optimal subproblem solutions.

Key Takeaways

To summarise, this article discusses the problem - Maximise Difference Between Sum Of Even And Odd-Indexed Elements Of A Subsequence. We discussed the problem briefly, the problem statement, the approach, followed by the solution code.

Check out this problem - Subarray With 0 Sum

If you wish to practice questions based on Dynamic Programming, you can visit Top Dynamic Programming Questions.

That’s all folks for this article. Until next time keep Coding !

Previous article
Longest Bitonic Subsequence
Next article
Maximum sum subsequence of any size that is decreasing-increasing alternatively
Live masterclass