A Simple Solution in Java. O(n) time and O(1) space;


  • 1
    S

    The basic idea is to treat the process to the Stock as couples states:
    never buy(nh0), first hold(h0), not hold one transaction before(nh1), hold and one transaction before(h1), not hold two transaction before(nh2).
    nh0,h0,nh1,h1,nh2 represents the max profit you could have at day i at corresponding status.

    Then the relationship between day i+1 and day i is quite simple. We have successfully make the status of day i+1 only related to day i. We can then compute it iteratively.

    public class Solution {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            int nh0=0;
            int h0=Integer.MIN_VALUE;
            int nh1=Integer.MIN_VALUE;
            int h1=Integer.MIN_VALUE;
            int nh2=Integer.MIN_VALUE;
            
            for (int i=0;i<n;i++)
            {
                int newh0 = Math.max(h0,-prices[i]);
                int newnh1= Math.max(nh1,newh0+prices[i]);
                int newh1 = Math.max(h1,newnh1-prices[i]);
                int newnh2 = Math.max(nh2,newh1+prices[i]);
                
                h0 = newh0;
                nh1 = newnh1;
                h1 = newh1;
                nh2 = newnh2;
            }
            return Math.max(nh0,Math.max(nh1,nh2));  
        }
    }

Log in to reply
 

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