Given a sequence of numbers, you have to find the maximum sum alternating subsequence and print the value

belongs to collection: interview C++ coding problems/challenges | dynamic programming

mahmoud2506

Save to bookmark

2022-05-01

270

Find the maximum sum alternating subsequence

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)

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-05-01

need an explanation for this answer? contact us directly to get an explanation for this answer

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,

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.
If any element is less than the current element then,
f(indexofthecurrentelement) = max⁡
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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)