阿亮的算法之路——122. 买卖股票的最佳时机 II

题目描述

题目连接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

一开始看到这个题目的时候，有点不知从何下手。想到了动态规划，当前可以获取的最高价格，可以从当前的价格和前几个可以获得的最高价格产生练习，但是我又想到了：万一后面的某个数很大，需要用这个最大的数去减去最小的那个数呢？那岂不是又要倒回去找最小的数？

其实是我想错了，正确的思路是：利用分段的思想。
因为后面的价格不能比前面的更大，更大的话，那么即便数组里多了这个价格，获得的最大利润也不会增加。例如：数组是{6,4,2,6,7,9,11}，那么，无论后面增加多少个值进来，只要比前一个大，就不会获得更多的利润。
所以，我们只要一组一组的去找，分组的依据就是，当后一个值比前一个值大，就开启一个组，直到后一个值比前一个值更小，这个组就结束了。

我画个图：
每个柱形的高度代表了数组的每个值，按照这个思路分组，再结合动态规划，记录前面的分组获取的利润，就能解题了

首次通过

按照上面的思路，写出了最初版本

    public static int maxProfit(int[] prices){int len = prices.length;if(len == 1) return 0;int[] dp = new int[len];dp[0] = 0;dp[1] = prices[1] - prices[0] >= 0 ? prices[1] - prices[0]:0;int lastMinIndex = prices[0] < prices[1] ? 0:1;for (int i = 2; i < len; i++){if (prices[i] < prices[i-1]){dp[i] = dp[i-1];lastMinIndex = i;}else{if (lastMinIndex == 0) { dp[i] = prices[i] - prices[lastMinIndex]; }else { dp[i] = dp[lastMinIndex-1] + (prices[i] - prices[lastMinIndex]); }}}return dp[len-1];}

提交结果
结果不是很理想，但是我觉得我的思路是没问题的，可能在一些地方的处理比较粗糙。
我透，同样的代码，一行没改过，我再次提交，和第一次提交的差别这么大
再提交一次
算了，就这样吧，这个数据不是很准确，而且的确也没想到要怎么优化，去看看大佬们的题解。

大佬题解

给出的解题思路和我想的是一样的，只不过我用了柱状图来说明，给出的题解用折线图来体现的，更加直观一些。
大佬们还给出了一种更简单的解决办法，是在前面解题思路的基础上进行简化的。

我们最终得到的利润是什么？s1+s2+s3+s4+s5，那s1、s2、s3、s4、s5又是怎么来的呢？如果一个组里只有两个数（如s1、s2、s3、s4），那么直接将这两个数相减就可以了。但如果是像s5那样，一个组里有多个数呢？其实还是可以拆成相邻两个数的差之和，s5是倒数第一个值减去倒数第二个之差 和 倒数第二个值与倒数第三个值之差 的和。

这样一来就简单了，只要后一个数比前一个数大，那么他们的差，就是利润的一部分，将所有部分加起来就是最终的利润。

代码

    public static 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;}

代码也忒简单了吧，一个循环，两三行就决绝了
而且这效率也很好，大致思路都是同样的，一点点小小的改变，就能简化这么多，这些思想的巧妙啊，究竟是天生智力所悟，还是经验积累而得呢？