leetcode

For this kind of problem, it is easy to get the idea that we can cut the whole space into several interval, and each interval is responsible for a new transaction.

Then we go forward and backward to calculated the two transaction.

public class Solution {
    public int maxProfit(int[] prices) {

        int len = prices.length;
        if(len == 0)return 0;

        int[] forward = forward(prices);
        int[] backward = backward(prices);

        int res = 0;



        for(int i = 0; i < len; i++){
            //System.out.println(i + " " + forward[i] + " " + backward[i]);

            int cur = forward[i] + backward[i];
            res = Math.max(res,cur);

        }
        return res;





    }

    public int[] forward(int[] prices){
        int[] res = new int[prices.length];
        int min = prices[0];

        for(int i = 1; i < prices.length; i++){
            res[i] = Math.max(prices[i] - min,res[i - 1]);
            min = Math.min(min,prices[i]);
        }

        return res;
    }

    public int[] backward(int[] prices){

        int len = prices.length;
        int[] res = new int[len];
        int max = prices[len - 1];

        for(int i = len - 2; i >= 0; i--){
            res[i] = Math.max(max - prices[i],res[i + 1]);
            max = Math.max(max,prices[i]);
        }
        return res;
    }

    public static void main(String[] args){
        Solution s = new Solution();
        int[] tester = new int[]{1,3,4,5,2,4,5,6};
        int res = s.maxProfit(tester);
        System.out.println(res);
    }
}