LeetCode122（买卖股票的最佳时机2）

发表于 | 分类于 ，

题目：

　　给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：

　　做出这道题需要理解：在每个波谷买入并且在每个波谷之后的波峰卖出（交易多次）所获得的收益肯定是大于或等于在最低点买入在最高点卖出（交易一次）所
获得的收益。明白了这一点就很好做出此题，即算出每个波谷波峰直接的差值，并相加即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 贪心算法
public int maxProfit2(int[] prices) {
	if (prices == null || prices.length < 2) {
		return 0;
	}
	int valley = prices[0];
	int peak = prices[0];
	int maxPro = 0;
	int i = 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];
		maxPro += peak-valley;
	}
	return maxPro;
}
// 优化方案
public int maxProfit1(int[] prices) {
	if (prices == null || prices.length < 2) {
		return 0;
	}
	int maxPro = 0;
	for(int i = 0;i < prices.length-1;i++) {
		if (prices[i] < prices[i+1]) {
			maxPro += prices[i+1] - prices[i];
		}
	}
	return maxPro;
}

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

原题链接：

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/