State transition idea. O(n)

  • 0
    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.