Very good DP one.
First I figured out a O(n^2) solution:
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if(!n) return 0; vector<int> dp(n); dp[0] = 0; for(int i = 1; i < n; i ++) { int vn = dp[i-1]; // nothing // sell int vs = 0, sofarMin = INT_MAX; for(int j = i - 1; j >= 0; j --) { sofarMin = min(sofarMin, prices[j]); int localProfit = prices[i] - sofarMin; int thisChoice = localProfit + (j >= 2? dp[j - 2] : 0); vs = max(vs, thisChoice); } int v = max(vn, vs); dp[i] = max(dp[i], v); } return dp.back(); } };
However by intuition, there must be a O(n) with smarter DP design. Yes!
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if(!n) return 0; vector<vector<int>> dp(n, vector<int>(3, 0)); // 0 buy, 1 rest, 2 sell dp[0][0] = -prices[0]; for(int i = 1; i < n; i ++) { dp[i][0] = max(-prices[i] + dp[i-1][1] /*buy on last rest*/, dp[i-1][0] /* update best buy so far*/); // buy this dp[i][2] = max( prices[i] + dp[i-1][0] /*sell on last buy*/, dp[i-1][2] /* update best sell so far*/); // sell this dp[i][1] = dp[i-1][2]; // rest this, somewhat greedy } return dp.back()[2]; // somewhat greedy } };
As you can see, dp[][] vars are rolling. So we don't have to use DP array. 3 vars is enough :) - as this link shows:
https://leetcode.com/discuss/71354/share-my-thinking-process