分享程序员开发的那些事...
更新时间：2022-06-08 18:59:15
Personally, this is a relatively difficult DP problem. This link posts a typical DP solution to it. You may need some time to get how it works.
The code is rewritten as follows.
1 class Solution { 2 public: 3 int maxProfit(vector<int>& prices) { 4 int n = prices.size(), num = 2; 5 if (n <= 1) return 0; 6 vector<vector<int> > dp(num + 1, vector<int>(n, 0)); 7 for (int k = 1; k <= num; k++) { 8 int temp = dp[k - 1][0] - prices[0]; 9 for (int i = 1; i < n; i++) { 10 dp[k][i] = max(dp[k][i - 1], prices[i] + temp); 11 temp = max(temp, dp[k - 1][i] - prices[i]); 12 } 13 } 14 return dp[num][n - 1]; 15 } 16 };
Personally, I prefer this solution, which is much easier to understand. The code is also rewritten as follows.
class Solution { public: int maxProfit(vector<int>& prices) { int states[2][4] = {INT_MIN, 0, INT_MIN, 0}; int n = prices.size(), cur = 0, next = 1; for (int i = 0; i < n; 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(cur, next); } return max(states[cur][1], states[cur][3]); } };