DP O(N) run time, beginner code, nothing fancy, thinking process and well commented.

  • 1

    First, I assume you know what to calculate the max if we can only do 1 transaction.

    if it's a constant increase, we don't need to sell
    if it's a constant decrease, we don't need by buy
    so if we have a decrease in the middle, we can consider selling the stock before the decrease.
    since we can only buy twice, we can't sell everytime the stock is go down.
    so how do we choose when to buy?

    We know how to calculate for one transaction.
    for 2 all we need to do is to split the array into 2 parts, so that the sum of each subpart is greatest.
    so the question now turn into how do we split the array.
    Even for constant decrease or constant increase, this should work.
    There are n way to split the array. each split will take n time to calculate the sum

    Actually, no, it's just O(n)
    we have 2 arrays, one store the max value from 0 to i, the other one store the value from i to length
    then we see what's the max at split at every spot in constant time.
    each array will take O(n) time to generate, so the entire will only take O(n)!

    public class Solution {
        public int maxProfit(int[] prices) {
            if(prices.length < 2) return 0;
            int[] firstHalf = new int[prices.length];
            int[] secondHalf = new int[prices.length];
            int current = 0;
            int max = 0;
            //calculate the max profit from day 1 to day i
            for(int i = 1; i < prices.length; i++){
                current = Math.max(0,current + prices[i] - prices[i-1]);
                max = Math.max(current, max);
                firstHalf[i] = max;
            //calculate the max profit from day i to day n, where n is the last day
            current = 0;
            max = 0;
            for(int i = prices.length - 1; i >0; i--){
                current = Math.max(0,current + prices[i] - prices[i-1]);
                max = Math.max(current, max);
                secondHalf[i-1] = max;
            //find the max at each split, we have the result!
            max = 0;
            for(int i = 0; i < prices.length; i++){
                max = Math.max(firstHalf[i]+secondHalf[i], max);
            return max;

Log in to reply

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