AlgoPressAppearance
0122-买卖股票的最佳时机II
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii
给定一个数组 prices ，其中prices[i] 是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 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。
提示： $$ 1 <= prices.length <= 3 * 10^4 0 <= prices[i] <= 10^4 $$
基本思路
题目要求尽量完成更多的买卖，所以我们先取得最小值，当出现比他大的值的时候，就买卖。 从数组 0 开始缓存 minPrice, 遍历后续记录，有两种情况
- prices[i]值小于 minPrice, 则更新当前值为 minPrice
- prices[i]值大于 minPrice, 则开始卖掉股票，获取利润，并且因为卖掉了，所以更新minPrice为当前股票值 继续循环，当后续有再大于 minPrice 的股票，则等于从prices[i]开始重新买入并后续卖出
参考代码
注意重点：卖出股票获取利润后要更新 minPrice 为当前值
csharp
public class Solution {
public int MaxProfit(int[] prices) {
int minPrice = prices[0];
int sumProfit = 0;
for(int i=1; i< prices.Length; i++){
if(minPrice > prices[i]){
minPrice = prices[i];
}
else{
int profit = prices[i] - minPrice;
sumProfit += profit;
minPrice = prices[i];
}
}
return sumProfit;
}
}
参考代码2：优化明天比今天大，就今天买入明天卖出
注意重点： 比如 [7, 1, 5, 6] 第二天买入，第四天卖出，收益最大（6-1），所以一般人可能会想，怎么判断不是第三天就卖出了呢? 这里就把问题复杂化了，根据题目的意思，当天卖出以后，当天还可以买入，所以其实可以第三天卖出，第三天买入，第四天又卖出（（5-1）+ （6-5） === 6 - 1）。所以算法可以直接简化为只要今天比昨天大，就卖出。
csharp
public class Solution{
public int MaxProfit(int[] prices){
int sumProfit = 0;
for(int i=0; i<prices.Length-1;i++){
if(prices[i] < prices[i+1]){
sumProfit+=prices[i+1] - prices[i];
}
}
return sumProfit;
}
}
复习代码：2022-04-02
csharp
public class Solution {
public int MaxProfit(int[] prices) {
int profit = 0;
int min = int.MaxValue;
for(int i = 0; i < prices.Length; i++){
if(prices[i] < min){
min = prices[i];
}
else{
//直接就计算利润，考虑两个情况
//1. 如果后面股票价格更低，则不影响结果，本地就是要卖掉获取利润的
//2. 如果后面股票价格更高，这里直接计算了 profit, 将当前价格设置为 min
// 这样也相当于累计了增加了前面已经计算的利润
profit += prices[i] - min;
min = prices[i];
}
}
return profit;
}
}
复习:20220513
csharp
public class Solution {
public int MaxProfit(int[] prices) {
int profit = 0;
int min = prices[0];
for(int i=1; i<prices.Length; i++){
if(prices[i] > min){
profit += prices[i]-min;
min = prices[i];
}
else{
min = prices[i];
}
}
return profit;
}
}
复习：20220515 贪心
csharp
public class Solution {
public int MaxProfit(int[] prices) {
int sum = 0;
for(int i=1; i<prices.Length; i++){
if(prices[i] > prices[i-1]){
sum+=prices[i] - prices[i-1];
}
}
return sum;
}
}
复习动规写法：重要，便于理解后面题目
csharp
public class Solution {
public int MaxProfit(int[] prices) {
int n = prices.Length;
int[,] dp = new int[n,2];
//dp[i,0] 表示第i天持有股票的利润
//dp[i,1] 表示第i天不持有股票的利润
dp[0,0] = -prices[0];
for(int i=1; i<n; i++){
dp[i,0] = Math.Max(dp[i-1,0], dp[i-1,1] - prices[i]); //此处要加入前面能获取的利润
dp[i,1] = Math.Max(dp[i-1,1], dp[i-1,0] + prices[i]);
}
return dp[n-1,1];
}
}