Home » Interview coding problems/challenges

Find the maximum sum alternating subsequence

Here, we are going to learn the solution to find the maximum sum alternating subsequence using dynamic programming.
Submitted by Souvik Saha, on June 25, 2020

Problem statement:

Given a sequence of numbers, you have to find the maximum sum alternating subsequence and print the value. A sequence is an alternating sequence when it will be maintain like (increasing) -> (decreasing) ->(increasing) ->(decreasing).

Input:
T Test case
T no. of input string will be given to you.

E.g.
3

2 3 4 8 2 5 6 8
2 3 4 8 2 6 5 4
6 5 9 2 10 77 5

Constrain:
1≤ A[i] ≤50

Output:
Print the value of maximum sum alternating subsequence.

Example

T=3

Input:
2 3 4 8 2 5 6 8 
Output:
22 ( 8+6+8)

Input:
2 3 4 8 2 6 5 4
Output:
20 ( 8+ 2+ 6+ 4)

Input:
6 5 9 2 10 77 5
Output:
98 (5+ 9+ 2+ 77+5)

Explanation with example:

Let N be the number of elements say, X1, X2, X3, ..., Xn

Let f(a) = the value at the index a of the increasing array, and g(a) = the value at the index a of the decreasing array.

To find out the maximum sum alternating sequence we will follow these steps,

1. We take two new arrays, one is increasing array and another is decreasing array and initialize it with 0. We start our algorithm with the second column. We check elements that are before the current element, with the current element.
2. If any element is less than the current element then,
   f(indexofthecurrentelement) = max⁡
3. If the element is greater than the current element then,
   g(indexofthecurrentelement) = max⁡

C++ Implementation:

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

int sum(int* arr, int n)
{
    int inc[n + 1], dec[n + 1];
    inc[0] = arr[0];
    dec[0] = arr[0];
    memset(inc, 0, sizeof(inc));
    memset(dec, 0, sizeof(dec));
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[i]) {
                dec[i] = max(dec[i], inc[j] + arr[i]);
            }
            else if (arr[i] > arr[j]) {
                inc[i] = max(inc[i], dec[j] + arr[i]);
            }
        }
    }
    return max(inc[n - 1], dec[n - 1]);
}

int main()
{
    int t;
    
    cout << "Test Case : ";
    cin >> t;
    
    while (t--) {
        int n;
    
        cout << "Number of element : ";
        cin >> n;
    
        int arr[n];
    
        cout << "Enter the elements : ";
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
    
        cout << "Sum of the alternating sequence : " << sum(arr, n) << endl;
    }
    
    return 0;
}

Output

Test Case : 3
Number of element : 8
Enter the elements : 2 3 4 8 2 5 6 8
Sum of the alternating sequence : 22
Number of element : 8              
Enter the elements : 2 3 4 8 2 6 5 4
Sum of the alternating sequence : 20
Number of element : 7
Enter the elements : 6 5 9 2 10 77 5
Sum of the alternating sequence : 98