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