题目Say you have an array for which theith element is the price of a given stock on dayi.Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).Note:You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).Example 1:Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price 1) and sell on day 3 (price 5), profit 5-1 4. Then buy on day 4 (price 3) and sell on day 5 (price 6), profit 6-3 3.Example 2:Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price 1) and sell on day 5 (price 5), profit 5-1 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.Example 3:Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit 0.这道题和上一道的差别就在于上一道题中只能进行一次交易一次买或一次卖但是这道题中可以进行多次交易其实也就是卖了以后过几天再买。由于提前看了之前的博客做了个小弊于是又不经过自己的思考就知道了答案……其实这种情况下每天只要发现比前一天的价格更高那么前一天就买入这神逻辑提前一天能预测到第二天的股价如果比今天高那就买今天的如果比今天低就不买每天都这么干最后的收益肯定是最大的。这种思路的代码如下运行时间8ms/100%空间9.5M/100%时间复杂度O(n)空间复杂度O(1)。class Solution { public: int maxProfit(vectorint prices) { int max_profit 0; for (int i 1; i prices.size(); i) { if (prices[i] - prices[i - 1] 0) { max_profit prices[i] - prices[i - 1]; } } return max_profit; } };看到discussion里面有很多人在质疑上面这种方法是否违背了“每天只能进行一次交易”的原则我觉得这怎么解释都解释得通吧如果要强行解释成每次加一次profit就相当于一次交易成功那确实这个方法违背了原则但实际操作上是可以等到达到最高点的时候再卖但是这又成了神仙买卖了你不仅能预知后一天的你还能预知所有计算范围内的最高价……但是呢这道题也只是说需要求出这样一个最大的profit如果只是求求的话也犯不着这么较真求出来不就完了嘛。所以此时又出现一种解法就比较良心但是复杂不会违背这个原则。大体意思是通过逐步遍历来找出当前的局部最小值作为买入的时间点再从这个局部最小值往后遍历找到接下来的局部最大值作为卖出的时间点直至遍历完成。代码如下运行时间8ms/100%空间9.4M/100%时间复杂度O(n)空间复杂度O(1)。class Solution { public: int maxProfit(vectorint prices) { if (prices.size() 0) { return 0; } int profit 0; int i 0; int buy, sell; while (i prices.size() - 1) { while (i prices.size() - 1 prices[i] prices[i 1]) { i; } buy prices[i]; while (i prices.size() - 1 prices[i] prices[i 1]) { i; } sell prices[i]; profit sell - buy; } return profit; } };2026.10.18就比较straightforward但是有点说不清道不明的感觉。class Solution { public int maxProfit(int[] prices) { int result 0; for (int i 1; i prices.length; i) { if (prices[i] prices[i - 1]) { result (prices[i] - prices[i - 1]); } } return result; } }