Perhaps the weirdest solution... (Java)


  • 0
    E

    This is far from standard/classic DP solution. I am posting it just for fun :)

    The idea is to scan from left to right and compute all possible states for every day i. All states on day i include:

    1. already sold=0, which includes following possible states
    • current has 0 and buy one on day i
    • current has 1 and do nothing
    • current has 1 and sell on day i
    1. already sold=1, which includes following possible states
    • current has 0 and buy one on day i
    • current has 0 and do nothing
    • current has 1 and do nothing
    • current has 1 and sell on day i

    A total of seven states. So the idea is to compute the maximum profit of all states...

    Code in Java:

    public class Solution {  
    public int maxProfit(int[] prices) {
        int L = prices.length;
        if(L<=1) return 0;
        int max = 0;
        int sell0_has0Buy = -prices[0];
        int sell0_has1Pause = -prices[0];
        int sell0_has1Sell = 0;
        int sell1_has0Buy = -prices[0];
        int sell1_has0Pause = 0;
        int sell1_has1Pause = -prices[0];
        int sell1_has1Sell = 0;
        for(int i=1; i<L; i++) {
        	int new_sell0_has0Buy = -prices[i];
        	int new_sell0_has1Pause = max(sell0_has1Pause, sell0_has0Buy);
        	int new_sell0_has1Sell = prices[i] + new_sell0_has1Pause;
        	int new_sell1_has0Pause = max(sell1_has0Pause, sell0_has1Sell);
        	int new_sell1_has0Buy = (-prices[i] + new_sell1_has0Pause);
        	int new_sell1_has1Pause = max(sell1_has1Pause, sell1_has0Buy);
        	int new_sell1_has1Sell = prices[i] + new_sell1_has1Pause;
            sell0_has0Buy = new_sell0_has0Buy;
        	sell0_has1Pause = new_sell0_has1Pause;
        	sell0_has1Sell = new_sell0_has1Sell;
        	sell1_has0Buy = new_sell1_has0Buy;
        	sell1_has0Pause = new_sell1_has0Pause;
        	sell1_has1Pause = new_sell1_has1Pause;
        	sell1_has1Sell = new_sell1_has1Sell;
        	int temp = max(sell0_has1Sell, sell1_has1Sell);
        	max = temp > max ? temp : max;
        }
        return max;
    }
    
    private int max(int a, int b) {
    	return a>b ? a : b;
    }
    }

Log in to reply
 

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