问题说明来源leetcode

一、问题描述:

122. 买卖股票的最佳时机 II

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。总利润为 4 。

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

二、题解：

思路：

一路下降是没办法的，一路上升还是有机会的。

那么一路上升时，怎么买呢？

对于一路上升，

1、如果我们买开头和结尾的那个来可以吗？

2、如果中间也买再在中间价格售出怎么样？会不会比1方案好？

事实上最好的应该是去峰峰值，在低谷时买到，再在最高点卖出是赚最多的，不管中间买卖了多少挣了多少，也都是比不上开头和结尾的：

因为手头上最多只能存1个股票，因此每次只能卖出去了才能再买股票。

就算再中间深刻买了很多股票，赚的肯定也是在最大差值以内的，不可能大于最大差值。而就算狠狠地买和卖也不行，因为买了得卖出去才可以买其他的，因此不断买和卖累加的结果是没办法填满最大差值的（最大差值指的是开头结尾买卖赚的）。这一段就是属于上升的

对于一路下降的肯定是不可能的。

于是得到一个假设：最大利润由每段递增坡度的最小买入，最大卖出得到。

当只有一段递增坡度时，肯定是的。那么当只有2段递增坡度呢？也就是中间有一段是递减的，也是对吧。

那么有4段呢？5段呢？n段？

如果n段时这样子可以得到最大利润，那么n+1可以？

证明一下。

当n段可以这么得来，那么n+1段坡度的总最大利润是有前n段递增的坡度加上第n+1段坡度的最大利润得来的。

前n段的总最大利润得到是s(n),第n+1段的最大利润是a(n + 1)

总最大利润s(n + 1)会不会是 s(n) + a(n + 1)呢？

是吗？左边找到总最大的利润s(n)了，再加上右边的那份利润应该是了吧？

而且找到最大利润都是局部最优得到全局最优的，如果砍掉第n+1个坡度，那么最大利润就是s(n)了，如果不砍掉，那么最大利润肯定是增加了，增加了的就是a(n + 1)

每个局部最优组成最大最优，感觉还是有些没论证，因为全局最优不一定等于局部最优累加，在一些特殊的例子里，可能那些例子是会对全局造成了其他影响了，但是这个题就是按照假设的来办就应该没问题了：

/*** @author xin麒* @date 2023/1/10 18:04*/
public class Solution {public int maxProfit(int[] prices) {int res = 0;int minNum = 0;if (prices.length == 1) return 0;int curr = prices[0];for (int i = 1; i < prices.length; i++) {if (curr > prices[i]){//说明是前一个大于后一个，处于递减坡度，找到最小赋予minNum,然后结束；while (i < prices.length){if (curr < prices[i]) break;curr = prices[i];i++;}i--;//如果是最后的递减坡度，那么i此时是len -1//找到最小的赋予curr即可}else if (curr < prices[i]){//说明是递增坡度，minNum = curr;//找到最大，赋予currwhile (i < prices.length){if (curr > prices[i]) break;//此时是最大值。（局部）curr = prices[i];i++;}i--;res += curr - minNum;}//如果是平谷，那么不用管。}return res;}
}

其实这道题是和376. 摆动序列很像的,曲线都是跌宕起伏的。