AlgoPressAppearance
0123-买卖股票的最佳时机III
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1]
输出：0
提示：
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 105
思路【有问题】
遍历数组，将所有可以成交的最大差值加入数组中去，最后从数组中取出最大的两个比交易值 有问题： [6,1,3,2,4,7]
代码
csharp
public class Solution {
public int MaxProfit(int[] prices) {
int min = prices[0];
List<int> profits = new List<int>();
int topProfit = 0;
int secondProfit = 0;
int profit = 0;
for(int i=1; i<prices.Length; i++){
if(prices[i] < min || prices[i] < prices[i-1]){
//此处应该是小于最小数，或者小于前一个数
min = prices[i];
//计算前面的 profit
if(profit >= topProfit){
secondProfit = topProfit;
topProfit = profit;
}
else if(profit > secondProfit){
secondProfit = profit;
}
profit = 0;
}
else{
//注意这里需要比较profit的大小，因为小的数字可能出现在后面
profit = Math.Max(prices[i] - min,profit);
Console.WriteLine("set profit:{0} = {1}",i,profit);
}
}
//最后再计算一次 profit
if(profit >= topProfit){
secondProfit = topProfit;
topProfit = profit;
//Console.WriteLine("set top profit = {0}",topProfit);
}
else if(profit > secondProfit){
secondProfit = profit;
}
return topProfit + secondProfit;
}
}
思路：暴力求解：会超时【错误】
设置某个时间点作为第一次股票卖出的时间，那么结果应该就是求出两次买卖累计的和最大
csharp
public class Solution {
public int MaxProfit(int[] prices) {
int maxProfit = 0;
for(int i=0; i<prices.Length; i++){
int part1 = MaxProfit(prices,0,i);
int part2 = MaxProfit(prices,i+1,prices.Length-1);
maxProfit = Math.Max(maxProfit,part1+part2);
}
return maxProfit;
}
private int MaxProfit(int[] prices, int start, int end){
if(start>=end){
return 0;
}
int min = prices[start];
int profit = 0;
for(int i=start; i<=end; i++){
if(prices[i] < min){
min = prices[i];
}
else{
profit = Math.Max(profit,prices[i]-min);
}
}
return profit;
}
}
思路：动态规划【官方】
由于我们最多可以完成两笔交易，因此在任意一天结束之后，我们会处于以下五个状态中的一种：
- 未进行过任何操作；
- 只进行过一次买操作；
- 进行了一次买操作和一次卖操作，即完成了一笔交易；
- 在完成了一笔交易的前提下，进行了第二次买操作；
- 完成了全部两笔交易。
第一种状态，利润为0，所以不记录。 我们记录 buy1, sell1, buy2, sell2 后四种状态情况下的最大利润
参考代码
csharp
public class Solution{
public int MaxProfit(int[] prices){
int buy1 = -prices[0];
int sell1 = 0;
int buy2 = -prices[0];
int sell2 = 0;
for(int i = 1; i < n; i++){
buy1 = Math.Max(buy1, -prices[i]); // 此处表示的是利润
sell1 = Math.Max(sell1, buy1 + prices[i]); // 第一次售卖的利润
buy2 = Math.Max(buy2, sell1 - prices[i]); // 第二次购买的利润，注意这里本来应该是 -prices[i] 可以合并上第一次售卖的利润
sell2 = Math.Max(sell2, buy2 + prices[i]);
}
return sell2;
}
}
//动态规划dp数组写法
public class Solution{
public MaxProfit(int[] prices){
int[,] dp = new int[prices.Length,4];
// dp[i,0] 表示买了第一支股票的最大利润
// dp[i,1] 表示卖了第一支股票的最大利润
// dp[i,2] 表示买了第二支股票的最大利润
// dp[i,3] 表示卖了第二支股票的最大利润
//初始化
dp[0,0] = -prices[0];
dp[0,1] = 0;
dp[0,2] = -prices[0];
dp[0,3] = 0;
for(int i=1; i<prices.Length; i++){
dp[i,0] = Math.Max(dp[i-1,0], -prices[i]); //如果我卖了价格高的股票，那么他的利润就低，因为还没有卖，所以利润是负
dp[i,1] = Math.Max(dp[i-1,1], dp[i-1,0] + prices[i]); //使用前面购买股票的利润+当前股票值，就是总的第一次卖的利润，取最大
dp[i,2] = Math.Max(dp[i-1,2], dp[i-1,1] - prices[i]); // 第二次售卖的利润，合并上第一次的利润进去
dp[i,3] = Math.Max(dp[i-1,3], dp[i,2] + prices[i]); // 计算第二次售卖的价格
}
return dp[prices.Length-1,3];
}
}
下面用最小值记录可以购买的点，更容易理解一点。
csharp
public class Solution{
public int MaxProfit(int[] prices){
int n = prices.Length;
int min1 = prices[0];
int profit1 = 0;
int min2 = prices[0];
int profit2 = 0;
for(int i = 1; i < n; i++){
//记录第一次可以购买的最小点
min1 = Math.Min(min1, prices[i]);
//计算第一次卖的利润，很容易理解
profit1 = Math.Max(profit1, prices[i] - min1);
//重点：buy2 中可以涵盖了第一次的利润，然后第二次相减的时候，包含了第一次的利润
//注意这里，可能还用第一次的最小值，如【1,2,3,4】 则整个就完成一次交易利润最大，而不是强制两次交易则利润是2
//等于 min2 中合并了第一个利润的已经得到的值 (此时min2的值有可能是负数)
min2 = Math.Min(min2, prices[i] - profit1);
profit2 = Math.Max(profit2, prices[i] - min2);
}
return profit2;
}
}
复习：20220630
csharp
public class Solution {
public int MaxProfit(int[] prices) {
int buy1 = -prices[0];
int sell1 = 0;
int buy2 = -prices[0];
int sell2 = 0;
for(int i=1; i<prices.Length; i++){
buy1 = Math.Max(buy1,-prices[i]); //当日买进
sell1 = Math.Max(sell1,buy1+prices[i]); //当日卖出
buy2 = Math.Max(buy2, sell1-prices[i]); //第二次买进(包含第一次的利润)
sell2 = Math.Max(sell2, buy2+prices[i]); //第二次卖出
//Console.WriteLine("buy1:{0},sell1:{1},buy2:{2},sell2:{3}",buy1,sell1,buy2,sell2);
}
return sell2;
}
}