LC_123

class Solution {
    // public int maxProfit(int[] prices) {
    //     if (prices.length==0) return 0;
    //     int K = 2;
    //     int[][] dp = new int[K+1][prices.length];
    //     for (int k=1 ; k<= K; k++) {
    //         for (int i=1; i<prices.length; i++) {
    //             int min = prices[0];
    //             for (int j=1;j<=i;j++) {
    //                 min = Math.min(min,prices[j]-dp[k-1][j-1]);
    //             }
    //             dp[k][i]=Math.max(dp[k][i-1], prices[i]-min);
    //         }
    //     }
    //     return dp[K][prices.length-1];
    // }
    public int maxProfit(int[] prices) {
        if (prices.length<=1) return 0;
        int[] dp = new int[prices.length];

        int min = prices[0];
        int max = 0;
        for (int i=1; i<prices.length;i++) {
            if ((prices[i]-min) > max) max = prices[i]-min;
            dp[i]=max;
            // System.out.println("max: "+max);
            if (min > prices[i]) min = prices[i];
        }
        // System.out.println("max: "+dp[dp.length-1]);
        // 2nd iteration
        max = prices[prices.length-1];
        int secProfit = 0;
        int totalMax = dp[prices.length-1], localMax;
        for (int i=prices.length-2; i>0; i--) {
            // System.out.println("processing index: "+i);
            if ((max-prices[i]) > secProfit) secProfit = max-prices[i];
            // System.out.println("sec profit: "+secProfit);
            localMax = dp[i-1]+secProfit;
            if (localMax > totalMax) totalMax = localMax;
            if (prices[i]>max) max = prices[i];
        }
        return totalMax;
    }
}