State transition idea. O(n)


  • 0
    B
    public class Solution {
        /* Inspired by dietpepsi's state transition idea in best time to buy and sell stock with cooldown. */
    
        public int maxProfit(int[] prices) {
            if (prices.length == 0) return 0;
            
            // You must in one of two states after you completed all transactions: buy state or sell state.
            int n = prices.length;
            
            // buy and sell array contains the max profit you have if you're in buy or sell state on i day.
            int[] buy = new int[n];
            int[] sell = new int[n];
            buy[0] = -prices[0];
            
            for (int i = 1; i < prices.length; i++) {
                // If you'er in the buy state on i day, you must transfer from the sell state or in buy state on i-1 day.
                buy[i] = Math.max(buy[i-1], sell[i-1]-prices[i]);
                
                // Same logic as buy[i]
                sell[i] = Math.max(buy[i-1]+prices[i], sell[i-1]);
            }
            
            return Math.max(sell[n-1], buy[n-1]);
        }
    }

Log in to reply
 

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