股票交易两次最大利润

作者: 大道至简_6a43 | 来源:发表于2020-09-04 23:50 被阅读0次

股票交易两次最大利润
买卖股票的最佳时机II
知识点5：财务目标（★）
大咖用一天的时间告诉你，如何从企业的成本转化为企业的资本
63 股票最大利润
导论：什么是公司理财and财务管理的目标
股票最大利润 II
股票最大利润 I
利润最大化
股票的最大利润

动态规划三维数组
在递归实现时，我们用了三个变量：index、status、k。这里我们定义一个三维数组
dp[n][3][2] 这里的n表示天数

dp[i][0][0]：表示第i天交易了0次时卖出后的累计最大利润
dp[i][0][1]：表示第i天交易了0次时买入后的累计最大利润
dp[i][1][0]：表示第i天交易了1次时卖出后的累计最大利润
dp[i][1][1]：表示第i天交易了1次时买入后的累计最大利润
dp[i][2][0]：表示第i天交易了2次时卖出后的累计最大利润
dp[i][2][1]：表示第i天交易了2次时买入后的累计最大利润
注意，最后一个dp[i][2][1] 实际是不存在的，因为交易两次后，就不能再买入了。

我们来分析一下上面定义的dp数组：

dp[i][0][0]：对应于初始状态，第i天0次交易卖出，既然都没交易，那何来卖出呢，所以只能是0。
dp[i][0][1]和dp[i][1][0] 这两个是一对，对应到上图中就是第一次买入、第一次卖出。
dp[i][1][1]和dp[i][2][0] 这两个也是一对，对应到上图中就是第二次买入、第二次卖出。
从这里我们也能看出为什么dp[i][2][1]是无效的。

再看一下状态转换公式如何推导的
前面我们分析过了，买入1这个状态只能从两个地方转换来，买入1本身(保持不动)，或者是初始状态转换而来。
而卖出1这个状态，也只能从两个地方转换而来，卖出1本身(保持不动)，或者从买入1转来。

那么根据上面描述，我们可以算出第一次买卖的DP公式：

第一次买入：从初始状态转换而来，或者第一次买入后保持不动
dp[i][0][1] = max(dp[i-1][0][1],dp[i-1][0][0]-prices[i])

第一次卖出：从第一次买入转换而来，或者第一次卖出后保持不动
dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][0][1]+prices[i])
再来分下一下第二次的买卖过程：
同样，第二次买入只能从第一次买入转换来，或者保持不动
第二次卖出只能从第二次买入转换来，或者保持不动

那么根据上面描述，我们可以算出第二次买卖的DP公式：

第二次买入：从第一次卖出转换而来，或者第二次买入后保持不动
dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][1][0]-prices[i])

第二次卖出：从第二次买入转换而来，或者第二次卖出后保持不动
dp[i][2][0] = max(dp[i-1][2][0],dp[i-1][1][1]+prices[i])
我们把第一次买卖、第二次买卖的DP公式合到一起，就拿到了完整的推导过程。
之后我们还需要处理一下第一天的初始化状态(具体请看代码部分)
最后求的利润最大值就保存在 dp[n-1][0][0]、dp[n-1][0][1]、dp[n-1][1][0]、dp[n-1][1][1]、dp[n-1][2][0]中，我们求出这几个值的max再返回就可以了。

代码实现:

javapython

class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length==0) {
return 0;
}
int n = prices.length;
//定义三维数组，第i天、交易了多少次、当前的买卖状态
int[][][] dp = new int[n][3][2];
//初始化第一天，这里的dp[0][2][1]可以不用管，后面也不会用到
dp[0][0][0] = 0;
dp[0][0][1] = -prices[0];//表示买了一次
dp[0][1][0] = 0;//表示当日买了又买了
dp[0][1][1] = -prices[0];//表示买了又卖了又买了
dp[0][2][0] = 0;//表示买了两次买了两次
dp[0][2][1] = -prices[0];//表示买了三次卖了两次
for(int i=1;i<n;++i) {
//dp[i][0][0]相当于初始状态，它只能从初始状态转换来
dp[i][0][0] = dp[i-1][0][0];
//处理第一次买入、第一次卖出
dp[i][0][1] = Math.max(dp[i-1][0][1],dp[i-1][0][0]-prices[i]);
dp[i][1][0] = Math.max(dp[i-1][1][0],dp[i-1][0][1]+prices[i]);
//处理第二次买入、第二次卖出
dp[i][1][1] = Math.max(dp[i-1][1][1],dp[i-1][1][0]-prices[i]);
dp[i][2][0] = Math.max(dp[i-1][2][0],dp[i-1][1][1]+prices[i]);
}
//返回最大值
int a = Math.max(dp[n-1][0][0],dp[n-1][0][1]);
int b = Math.max(dp[n-1][1][0],dp[n-1][1][1]);
return Math.max(Math.max(a,b),dp[n-1][2][0]);
}
}