leetcode 188 买卖股票的最佳时机 IV 不超过m个不相交子段和最大值

缘起

继续沉迷股票~ leetcode 188. 买卖股票的最佳时机 IV

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

本题是【1】的推广, 【1】中仅仅要求不能超过2笔交易, 这里是k笔.

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
typedef vector<int>::iterator vit;
public:
	int maxProfit(int k, vector<int>& prices) 
	{
		n = prices.size();
		for (int i = 1;i<n;i++)
		{
			a[i] = prices[i]-prices[i-1];
		}
		--n;
		for (int i = 1; i<=n; i++)
		{
			s[i] = s[i-1]+a[i];
		}
		int ans = 0;
		for (int i = 1;i<=k; i++) // 照搬【1】
		{
			if (i>n)
			{
				break;
			}
			ans = max(ans, kk(i));
		}
		return ans;
	}
	static const int maxn = 100005;
	int a[maxn], s[maxn], n, dp[maxn];

	int kk(int m)
	{
		dp[1] = a[1];
		for (int j = 2; j<=n; j++)
		{
			dp[j] = max(dp[j-1], 0)+a[j];
		} 
		for (int i = 2,t,x; i<=m; i++)
		{
			x = dp[i];
			dp[i] = s[i];
			t = s[i-1]; 
			for (int j = i+1; j<=n; j++)
			{
				t = max(t, x);
				x = dp[j];
				dp[j] = max(dp[j-1], t) + a[j];
			}
		}
		int ans = 0;
		for (int i = m; i<=n; i++)
		{
			ans = max(ans, dp[i]);
		}
		return ans;
	}
	
};

很遗憾, 上面的代码被T掉了. 因为照搬【1】就不得不引入for循环——上面代码的17行. 所以k一旦大了被T是显然的~

但是上面的代码211个测试点推广了208个, 可见算法应该是不会wa的. 只是超时而已. 所以不能照搬【1】. 必须要改变dp的意义. 但是依旧沿用 【2】的思想. 这一点和【1】是一样的.

1
2
3
4
5
6
7
dp[i][j]是a[1,..,j]以a[j]为结尾的不超过i个不交片段的最大和. 则dp方程和【2】几乎是一样的. 
dp[i][j] = max{dp[i][j-1],0,max_{1<=k<=j-1}{dp[i-1][k]}}+a[j], 1<i<=j<=n,i<=m
注意0的存在, 因为可以不选任何a[j]前面的元素
仅仅在k的范围与【2】不同。这是因为这里dp的意义变了
【2】中dp[i][j]是a[1,..,j]以a[j]为结尾的=i个不交片段的最大和,所以那里 i-1<=k<=j-1
而这里是不超过i个不交片段, 所以k自然可以到1去.
dp的初始化值是dp[1][j] 1<=j<=n, 这一点和【2】是一样的.

具体处理比较细节（和【2】一样）. 首先, 我们的dp方程是在上面给出了. 和【2】一样也要使用滚动数组优化空间. 然后我们得想办法O(1)维护 max_{1<=k<=j-1}{dp[i-1][k]}, 而dp方程是从 j=i 开始, 即j=i+1的状态要从j=i的状态推导出来. 而j=i+1的时候, max(0,max_{1<=k<=j-1}{dp[i-1][k]}} = max(0,max_{1<=k<=i}{dp[i-1][k]}) = max(0, max{1<=k<=i-1}{dp[i-1][k]}, dp[i-1][i]), 而和【2】一样, 我们将 dp[i-1][i] 赋值给x（即下面代码的第33行, 33行的dp[i]其实就是 dp[i-1][i] 你能感受的到吧~）, 从而我们只需要将 max(0,max{1<=k<=i-1}{dp[i-1][k]}) 赋给 t就行了（代码第34行）, 则第37行 t = max(t,x) 得到的就是 j=i+1的时候的max(0,max_{1<=k<=j-1}{dp[i-1][k]}) . 这和【2】是一样的手段. 但是 max(0,max{1<=k<=i-1}{dp[i-1][k]) = max(0,max{dp[1][1], dp[2][2],…,dp[i-1][i-1]}). 但是 dp[i][i] (1<=i<=n) 们是有关系的!

1
2
3
4
5
dp[i][i] = max{0,dp[1][1],...,dp[i-1][i-1]}+a[i], 注意0, 因为我完全可以不选a[i]前面任何一个
元素, 所以
max{0,dp[1][1],...,dp[i-1][i-1]} = dp[i][i]-a[i]
即t = dp[i][i]-a[i]
这就是代码第34行

遵照上面的改进dp, 不难写下如下ac代码（代码没怎么写注释, 详细注释见【2】）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
	int maxProfit(int k, vector<int>& prices) 
	{
		if (!k) // 特判一下,wa了一发
		{
			return 0;
		}
		n = prices.size();
		for (int i = 1;i<n;i++)
		{
			a[i] = prices[i]-prices[i-1];
		}
		--n;
		dp[1] = a[1];
		for (int j = 2; j<=n; j++)
		{
			dp[j] = max(dp[j-1], 0)+a[j];
		} // 和【2】一样的dp初始化
		int t = 0;
		dd[0] = 0;
		for (int i = 1;i<=n; i++)
		{
			dd[i] = a[i]+max(t, dd[i-1]); // 快速维护max{dp[k][k] | 1<=k<i}
			t = max(t, dd[i]);
		} // 预处理出 dd[i] = dp[i][i], 1<=i<=n
		for (int i = 2,t,x;i<=k;i++)
		{
			if (i>=n)
			{
				break;
			}
			x = dp[i];
			t = dd[i]-a[i];
			for (int j = i+1;j<=n;j++)
			{
				t=max(t,x);
				x = dp[j];
				dp[j] = max(dp[j-1], t)+a[j];
			}
		}
		int ans = 0;
		for (int i = 1;i<=n; i++)
		{
			ans = max(ans, dp[i]);
		}
		return ans;
	}

	const static int maxn = 50005;
	int a[maxn], n, s[maxn], dp[maxn], dd[maxn]; // dd[i] 就是 dp[i][i], 它需要被预处理出来
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
692 ms
, 在所有 cpp 提交中击败了
11.45%
的用户
内存消耗 :
9.6 MB
, 在所有 cpp 提交中击败了
20.26%
的用户

参考

【1】https://yfsyfs.github.io/2019/10/23/leetcode-123-买卖股票的最佳时机-III/

【2】https://yfsyfs.github.io/2019/09/12/hdu-1024-Max-Sum-Plus-Plus-m%E6%AE%B5%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E5%AD%90%E6%AE%B5%E5%92%8C%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC/