Q:

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

0

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)

All Answers

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,

  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

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

total answers (1)

interview C++ coding problems/challenges | dynamic programming

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now
A list of n days is given to you and there are thr... >>
<< Given a string str, find total number of possible ...