企业官网建设流程全解析

题目：

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(vector<int>& 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(vector<int>& 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; } }