My C++ solution (O(N) time, O(1) space, 8ms)

  • 90

    It is similar to other buy/sell problems. just do DP and define an array of states to track the current maximum profits at different stages. For example, in the below code

    • states[][0]: one buy
    • states[][1]: one buy, one sell
    • states[][2]: two buys, one sell
    • states[][3]: two buy, two sells

    The states transistions occurs when buy/sell operations are executed. For example, state[][0] can move to state[][1] via one sell operation.

    class Solution {
        int maxProfit(vector<int>& prices) {
            int states[2][4] = {INT_MIN, 0, INT_MIN, 0}; // 0: 1 buy, 1: one buy/sell, 2: 2 buys/1 sell, 3, 2 buys/sells
            int len = prices.size(), i, cur = 0, next =1;
            for(i=0; i<len; ++i)
                states[next][0] = max(states[cur][0], -prices[i]);
                states[next][1] = max(states[cur][1], states[cur][0]+prices[i]);
                states[next][2] = max(states[cur][2], states[cur][1]-prices[i]);
                states[next][3] = max(states[cur][3], states[cur][2]+prices[i]);
                swap(next, cur);
            return max(states[cur][1], states[cur][3]);

  • 7

    very good solution. one small improvement can be calculate state 3 first and 0 last in the loop. This way you only need 4 variables.

  • 1

    Wow, really good solution! The nicely-designed states and the meaningful names make the code very readable. BTW, the initialization of states and swap(next, cur) are so clever :-)

  • 0

    I have tried your improvement. But the running time is larger than the original implementation. The four statements can be paralleled while the enhancement cannot.

  • 0

    i c. Another space vs performance trade off.

  • 0

    can you explain more?

  • 5

    Thanks for sharing your idea. I was just thinking that the return statement can just be

    return states[cur][3]

    Because the only case, that one transaction or no transaction is better than two transactions is that, the vector is linear growth or linear decrease. And by these two situation, states[cur][3] will be the best value based on the initial value of states.

  • 0

    the buy/sell state (row) looks redundant to me

  • 0

    I've also tried that improvement but the running time did not go larger. Just reverse the order of the four statements and they can be still paralleled. I don't understand why here is a trade-off. Is anything I got wrong?

  • 0

    Though use same idea but four more space than the highest voted code, your code is more understandable. Thanks!

  • 0

    Excellent solution!

  • 0

    That's a really cool solution. With a little bit extra space, it is like a breeze. As @dietpepsi said: "Be generous when you think, and be greedy when you implement". It's very easy to reverse the four statements to get a four variables such as:

    states[3] = max(states[3], states[2] + prices[i]);
    states[2] = max(states[2], states[1] - prices[i]);
    states[1] = max(states[1], states[0] + prices[i]);
    states[0] = max(states[0], -prices);

  • 0

    very clear!!

Log in to reply

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