LeetCode 122 Best Time to Buy and Sell Stock II

LeetCode 122 Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the i<sup>th</sup> day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [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.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [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.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

`1 <= prices.length <= 3 10⁴*0 <= prices[i] <= 10⁴`

题目大意：

设计一个算法寻找最大收益。你可以随便完成多少次交易（比如，多次买入卖出）。然而你不能一次进行多次交易。

解题思路：

仍然是求最大利润，可以交易多次，但要先卖再买。容易想到是求所有上升坡的的总和。更简单而言，若将每一个上升坡，分成一小段(每天的交易)，求这些小段的和即可。
如：[6, 1, 2, 3, 4]中的1, 2, 3, 4序列来说，对于两种操作方案：
1 在1买入，4卖出
2 在1买入，2卖出同时买入，3卖出同时买入，4卖出
这两种操作下，收益是一样的。这种方法，避免检测下坡以及计算每段的和。

Python代码：

def maxProfit(self, prices: List[int]) -> int:
	res = 0
	for i in range(1, len(prices)):
		if prices[i] - prices[i - 1] > 0:
			res += prices[i] - prices[i - 1]
	return res

注意事项：

数组为空

Java代码：

public int maxProfit(int[] prices) {
	if(prices.length==0)
		return 0;
	int profit = 0;
	for(int i=1;i<prices.length;i++){
		if(prices[i-1]<prices[i])
			profit += prices[i] - prices[i-1];
	}
	return profit;
}

算法分析：

时间复杂度为O(n)，n为字符串长度，空间复杂度O(1)。

KK's blog