http://www.geeksforgeeks.org/maximum-sum-alternating-subsequence-sum
Given an array, the task is to find sum of maximum sum alternating subsequence starting with first element. Here alternating sequence means first decreasing, then increasing, then decreasing, … For example 10, 5, 14, 3 is an alternating sequence.
Note that the reverse type of sequence (increasing – decreasing – increasing -…) is not considered alternating here.
This problem is similar to Longest Increasing Subsequence (LIS) problem. and can be solved using Dynamic Programming.
We maintain two arrays
dp[i] : Stores sum of maximum sum alternating subsequence
starting with first element and ending with arr[i].
smaller[i] : True if next expected element in the maximum sum
alternating subsequence starting with first
element and ending with arr[i] is smaller than
arr[i].
False otherwise.
dp[i] can be written as:
dp[i] = arr[i] + max( dp[j] ) where 0 < j < i and
(arr[j] < arr[i] & flag[j] = True)
OR
(arr[j] > arr[i] & flag[j] = False)
Final result is maximum of all dp[] values.
int maxAlternateSum(int arr[], int n){ // dp[i] is going to sum of maximum of alternating // sequence that must end with arr[i] int dp[n]; // smaller[i] is going to store expected sign of // next element in the alternating subsequence that // includes arr[i] smaller[i] = 1 indicates next // expected element is smaller and smaller[0] = 0 // indicates that next expected element is greater. int smaller[n]; dp[0] = arr[0]; // As per question, first element must // be part of solution. smaller[0] = 1; // As per question, the alternating seq // must begin with decreasing part. // Traverse remaining elements and compute dp[i] for them for (int i = 1; i < n ; i++) { // Since we want max sum, we initialize current max // ending with i as minus infinite. dp[i] = INT_MIN; // Repeatedly check from first element as we can // get maximum sum by including any element for (int j=0; j<i; j++) { // If next expected element for arr[j] is smaller if (smaller[j] == 1) { // Check if element is actually smaller if (arr[i] < arr[j]) { // Store the max sum till that element dp[i] = max(dp[i], dp[j] + arr[i]); // Store the complement of flag as we want // next element larger than current smaller[i] = ! smaller[j]; } } else { // If next expected element for arr[j] is greater if (arr[j] < arr[i]) { // Store the max sum till that element dp[i] = max (dp[i], dp[j] + arr[i]); // Store the complement of flag as we want next // element smaller than current smaller[i] = ! smaller[j]; } } } } // Result is maximum of all values in dp[] int result = dp[0]; for (int i=1; i<n; i++) if (result < dp[i]) result = dp[i]; return result;}