My C++ O(N) DP algorithm 8ms (Finite State Machine based)


  • 4
    D

    The basic idea is to define a finite state machine (FSM) to describe the state at each step
    S_BUY (nothing to sell, but can buy), S_SELL (can sell, but can not buy), S_COOL (in cooldown mode, i.e. previous operation is SELL). S_BUY can go to S_BUY (do nothing at this step) or S_SELL (i.e. buy at this step); S_SELL can go to S_SELL(do nothing at this step) or S_COOL (SELL at this step); S_COOL can only move to S_BUY (do nothing at this step). With such FSM defined, one can move forward step by step to update the state array, which describes the profits at each possible state. Complexity is O(3*N)

    class Solution {
    private:
        const int STATE_NUM =3, STEP_NUM = 2, S_BUY=0, S_SELL=1, S_COOL=2;
    public:
        int maxProfit(vector<int>& prices) {
            int state[STATE_NUM][STEP_NUM], i, j, steps = prices.size(),cur=0, next=1;
            fill_n(&state[0][0], STATE_NUM*STEP_NUM, INT_MIN);
            for(i=0,state[0][0]=0;i<steps;++i, swap(cur, next))
            {
                state[S_BUY][next]  = max(state[S_BUY][cur], state[S_COOL][cur]);
                state[S_SELL][next] = max(state[S_BUY][cur]-prices[i], state[S_SELL][cur]);
                state[S_COOL][next] = state[S_SELL][cur] + prices[i];
            }
            return max(state[S_BUY][cur], state[S_COOL][cur]);
        }
    };

  • 0
    C
    This post is deleted!

Log in to reply
 

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