A simple Java Solution


  • 0
    F

    Sorry for my poor English.

    public class Solution {
        public int maxProfit(int[] prices) {
            if (prices.length == 0) return 0;
            int n = prices.length, i;
            // maxPrice[i] records maxprice in i..n
            int[] maxPrice = new int[n];
            maxPrice[n - 1] = prices[n - 1];
            for (i = n - 2; i >= 0; i--) {
                maxPrice[i] = Math.max(prices[i], maxPrice[i + 1]);
            }
            int min = Integer.MAX_VALUE, stock1Max = 0, max = 0;
            // i means buy the second stock on day i, the max profit of the second stock is maxPrice[i] - prices[i]
            // the first stock is the same as Best Time to Buy and Sell Stock I
            for (i = 0; i < n; i++) {
                stock1Max = Math.max(stock1Max, prices[i] - min);
                min = Math.min(min, prices[i]);
                max = Math.max(max, stock1Max + maxPrice[i] - prices[i]);
            }
            return max;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.