【leetcode】Best Time to Buy and Sell Stock IV

地址

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

题目

Say you have an array for which the i-th 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.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

1
2
3
Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

1
2
3
4
Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

思路

dp[i][j]表示:以i结尾时,进行了j次交易时的利润。(这里我把买入和卖出分别算一次交易,所以j为奇数时表示已买入一个股票 ,j为偶数时表示之前购买的股票全部卖出了)。

j==1: dp[i][j]=max{dp[i-1][j], dp[i-1][j-1]-prices[i], -prices[i]}, 0<i;

j==0:dp[i][j]=max{dp[i-1][j], dp[i-1][j-1]+prices[i]}, i>0;

代码里用了滚动数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int dp[2][100000];
int n = prices.size();
int ans = 0;
memset(dp, 0, sizeof dp);
k=min(n,k*2);
int now=0;
for(int i=0;i<n;++i,now^=1)
{
for(int j=1;j<=k;++j)
if(j&1)
{
dp[now][j] = -prices[i];
if(i>0)
dp[now][j] = max(dp[now][j], max(dp[now^1][j], dp[now^1][j-1]-prices[i]));
}
else
{
if(i>0)
dp[now][j] = max(dp[now][j], max(dp[now^1][j],dp[now^1][j-1]+prices[i]));

}

//for(int j=1;j<=k;++j)
// printf("%d%c",dp[i][j],j==k?'\n':' ');
}
for(int i=2;i<=k&&n>1;i+=2)
ans=max(ans, dp[now^1][i]);
return ans;
}
};