Dynamic Programming in a New Avatar: Part 2

class Solution {
    public int wiggleMaxLength(int[] a) {
        /*
        Solution
        1. Subproblems
            -> suffix[i:] - Number of sub-problems = O(n)
        2. Guess solution of subproblem
            -> at the ith position , we need to check if a[i] can be added to our existing subsequence.
            -> we would also need an additional variable called flag which can be 0 or 1. 
                -> 0 means we need to decrease the subsequence
                -> 1 means we need to increase the subsequence
            -> the condition to check is if flag is 0 and a[i] < a[i+1] or flag is 1 a[i] > a[i+1] then we add it 
            to the subsequence else we pass it to the next index.
        3. Recurrence
            -> DP(i, 0) = Math.max { 
                if(flag == 0 && a[i] > a[j]) // means it wants next number increasing
                    DP(i+1, 1) + 1
                else if(flag == 1 && a[i] < a[j]) // means it wants next number decreasing
                    DP(i+1, 0) + 1
                else
                    DP(i+1, 0) or DP(i+1, 1)
            }
        Time complexity - No of sub-problems * Time for each sub-problem = O(n) * O(1) = O(n)

        4. Topological sort - this problem can be represented using DAG, hence iterative way to write is

        DP[n][0][n-1] = DP[n][1][n-1] = 0 // for either flag we say we there is no subsequence as subsequence has ended.
        for (i in range n-1 to 0): 
            if(a[i] < a[i+1])            
                DP[i][0] = Math.max(DP[i+1][1] + 1, DP[i+1][0]);
            else if(a[i] > a[i+1])
                DP[i][1] = Math.max(DP[i+1][0] + 1, DP[i+1][1]);
            else
                DP[i][0] = DP[i+1][0];
                DP[i][1] = DP[i+1][1];

        5. Original Solution is Math.max(DP[0][0], DP[0][1])
        */        

        int n = a.length;
        int[][] DP = new int[n][2];
        DP[n-1][0] = DP[n-1][1] = 1;
        for(int i = n-2; i >= 0; i--){
            if(a[i] < a[i+1]){
                DP[i][0] = Math.max(DP[i+1][1] + 1, DP[i+1][0]);
                DP[i][1] = DP[i+1][1];
            }
            else if(a[i] > a[i+1]){
                DP[i][1] = Math.max(DP[i+1][0] + 1, DP[i+1][1]);    
                DP[i][0] = DP[i+1][0];
            }
            else {
                DP[i][0] = DP[i+1][0];
                DP[i][1] = DP[i+1][1];
            }
        }
        return Math.max(DP[0][0], DP[0][1]);
    }
}