Maximum sum alternating subsequence

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.

Examples:

Input :  arr[] = {4, 3, 8, 5, 3, 8}  
Output :  28
Explanation:
The alternating subsequence (starting with first element) 
that has above maximum sum is {4, 3, 8, 5, 8}

Input : arr[] = {4, 8, 2, 5, 6, 8} 
Output :  14
The alternating subsequence (starting with first element) 
that has above maximum sum is {4, 2, 8}

class Solution {
    // Return sum of maximum sum alternating sequence starting with arr[0] and is
    // first decreasing.
    public int maxAlternateSum(int arr[], int n) {
        if (n == 1)
            return arr[0];
        // dec[i] -> Max sum of subsequence, ending at i & decreasing in last step
        // (including i)
        int dec[] = new int[n];
        // inc[i] -> Max sum of subsequence, ending at i & increasing in last step
        // (including i)
        int inc[] = new int[n];
        // We have to include 0th element, doing this here and not as base case for
        // every element, makes sure that 0th element is in every sequence
        dec[0] = inc[0] = arr[0];
        // Flag -> Just to make sure we take decreasing step first
        int flag = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[i]) {
                    dec[i] = Math.max(dec[i], inc[j] + arr[i]);
                    // First decreasing step found, flag should be switched off
                    flag = 1;
                }
                // If increasing order is found, and flag is switched off
                else if (arr[j] < arr[i] && flag == 1)
                    inc[i] = Math.max(inc[i], dec[j] + arr[i]);
            }
        }
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++)
            result = Math.max(result, Math.max(inc[i], dec[i]));
        return result;
    }
}