State machine is the easiest way to understand stock problem, could solve all the stock problem in leetcode


  • 11
    P

    looking for the state machine picture, please click here

    inspired from this link

      class Solution {
        public:
            int maxProfit(int k, vector<int>& prices) {
                int m = prices.size();
                if(m==0 || m==1 || k == 0) return 0;
                if (k>m/2){ // simple case
                    int ans = 0;
                    for (int i=1; i<m; ++i){
                        ans += max(prices[i] - prices[i-1],0);
                    }
                    return ans;
                }
                vector<vector<int>> buy(k+1,vector<int>(m+1,0));
                vector<vector<int>> sell(k+1,vector<int>(m+1,0));
                vector<int> end(m+1,0);
                for(int i=1;i<=k;i++)
                    buy[i][0] = INT_MIN;
                for(int i=1;i<=m;i++){
                    for(int j=1;j<=k;j++){
                        //for the first buy state, need to compare the current price with the previous price. sell[0][0] are all initialized with 0, then sell[0][0] - prices[i-1] is the price of current first buy state
                        buy[j][i] = max(buy[j][i-1], sell[j-1][i-1] - prices[i-1]);
                        sell[j][i] = max(buy[j][i-1]+prices[i-1],sell[j][i-1]);
                    }
                }
                return sell[k][m];
            }
        };
    

  • 0
    R

    Why is it prices[i - 1] rather than prices[i] since you sold on day i - 1. Shouldn't you only be able to buy after the day you sell and likewise sell after you buy?


Log in to reply
 

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