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[i1], dp2[i1] + 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[i1], dp1[i1]  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[N1] and dp2[N1].
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

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.

How to convert the recursive solution to a dynamic approachbased solution?
If we have repeated subproblems in the recursive solution, that solution can be further optimized by applying memoization. The memoizationbased solution can be further converted to a dynamic programming approach. For more insights about memoization and dynamic programming, you can visit here.

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 OddIndexed 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 !