[123]best time to buy stock iii

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