Say you have an array for which the i element is the price of a given stock on day i.
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.
求解
方法一：暴力法
这种情况下，我们只需要计算与所有可能的交易组合相对应的利润，并找出它们中的最大利润。
因为不限制交易次数，在每一天，我就可以根据当前是否持有股票选择相应的操作。“暴力搜索” 也叫 “回溯搜索”、“回溯法”，首先画出树形图：
public class Solution {private int res;public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) {return 0;}this.res = 0;dfs(prices, 0, len, 0, res);return this.res;}/*** @param prices 股价数组* @param index 当前是第几天，从 0 开始* @param status 0 表示不持有股票，1表示持有股票，* @param profit 当前收益*/private void dfs(int[] prices, int index, int len, int status, int profit) {if (index == len) {this.res = Math.max(this.res, profit);return;}dfs(prices, index + 1, len, status, profit);if (status == 0) {// 可以尝试转向 1dfs(prices, index + 1, len, 1, profit - prices[index]);} else {// 此时 status == 1，可以尝试转向 0dfs(prices, index + 1, len, 0, profit + prices[index]);}}}
复杂度分析
- 时间复杂度：
，调用递归函数 
次。 - 空间复杂度：
，递归的深度为 
。
方法二：峰谷法
本方法可以获得买入卖出的时间点
假设给定的数组为：
[7, 1, 5, 3, 6, 4]
如果我们在图表上绘制给定数组中的数字，我们将会得到：
如果我们分析图表，那么我们的兴趣点是连续的峰和谷。
用数学语言描述为：
关键是我们需要考虑到紧跟谷的每一个峰值以最大化利润。如果我们试图跳过其中一个峰值来获取更多利润，那么我们最终将失去其中一笔交易中获得的利润，从而导致总利润的降低。<br /> 例如，在上述情况下，如果我们跳过  和 ， 试图通过考虑差异较大的点以获取更多的利润，然而获得的净利润总是会小与包含它们而获得的静利润，因为 C 总是小于 A+B。
class Solution {
public int maxProfit(int[] prices) {
int i = 0;
int valley = prices[0];
int peak = prices[0];
int maxprofit = 0;
while (i < prices.length - 1) {
while (i < prices.length - 1 && prices[i] >= prices[i + 1])
i++;
valley = prices[i];
while (i < prices.length - 1 && prices[i] <= prices[i + 1])
i++;
peak = prices[i];
maxprofit += peak - valley;
}
return maxprofit;
}
}
复杂度分析
- 时间复杂度：O(n)。遍历一次。
- 空间复杂度：O(1)。需要常量的空间。
方法三：简单的一次遍历(也有称差分)
该解决方案遵循 方法二 的本身使用的逻辑，但有一些轻微的变化。在这种情况下，我们可以简单地继续在斜坡上爬升并持续增加从连续交易中获得的利润，而不是在谷之后寻找每个峰值。最后，我们将有效地使用峰值和谷值，但我们不需要跟踪峰值和谷值对应的成本以及最大利润，但我们可以直接继续增加加数组的连续数字之间的差值，如果第二个数字大于第一个数字，我们获得的总和将是最大利润。这种方法将简化解决方案。
这个例子可以更清楚地展现上述情况：
[1, 7, 2, 3, 6, 7, 6, 7]
与此数组对应的图形是：
从上图中，我们可以观察到 A+B+C 的和等于差值 D 所对应的连续峰和谷的高度之差。
class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1])
maxprofit += prices[i] - prices[i - 1];
}
return maxprofit;
}
}
复杂度分析
- 时间复杂度：O(n)，遍历一次。
- 空间复杂度：O(1)，需要常量的空间。
若有收获，就点个赞吧
0 人点赞
