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

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 !