Leetcode 188. Best Time to Buy and Sell Stock IV

188. Best Time to Buy and Sell Stock IV

Total Accepted: 31463
Total Submissions: 135777
Difficulty: Hard

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

思路：DP，各变量的含义见代码。

代码：

 1 class Solution {
 2 public:
 3     int maxProfit(int k, vector<int> &prices) {
 4         int n = prices.size();
 5         if (k * 2 >= n) {
 6             int res = 0;
 7             for (int i = 1; i < n; i++) {
 8                 res += prices[i] > prices[i-1] ? prices[i] - prices[i-1] : 0;
 9             }
10             return res;
11         }
12         vector<vector<int> > dp(k + 1, vector<int>(n, 0));
13         //一次交易是先买入再卖出的一个完正过程
14         //dp[i][0]意味着只能当天买入卖出，所以dp[i][0]=0
15         //dp[0][i]意味着没有交易的次数，所以dp[0][i]=0
16         for (int i = 1; i <= k; i++) {
17             int localmax = -prices[0];
18             for (int j = 1; j < n; j++) {
19                 //dp[i][j] 表示的是前j天最多使用i次交易时（第j天可以卖出）的利润。（1<=i<=k，0<=j<n）
20                 dp[i][j] = max(dp[i][j-1], localmax + prices[j]);
21                 //localmax表示的是最多使用i次交易，使用最多前j-1个价格，最后买入price[j]后的最大利润
22                 localmax = max(localmax, dp[i-1][j-1] - prices[j]);
23             }
24         }
25         return dp[k][n-1];
26     }
27 };