## Monday, December 19, 2016

### Maximum sum alternating subsequence

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;`
`}`