题目
给定一个数组,它的第i
个元素是一支给定股票第i
天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例1
- 输入: [7,1,5,3,6,4]
- 输出: 7
- 解释: 在第2天(股票价格 = 1)的时候买入,在第3天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后,在第4天(股票价格 = 3)的时候买入,在第5天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例2
- 输入: [1,2,3,4,5]
- 输出: 4
- 解释: 在第1天(股票价格 = 1)的时候买入,在第5天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第1天和第2天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例3
- 输入: [7,6,4,3,1]
- 输出: 0
- 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
思路
- 首先,我们手上只能有一支股票,根据题目可知,要想产生利润,必须得是前一天股票的价值小于第二天的,这样我们的差值才会大于
0
。 - 把数组分成一个个递增的小片段,当有值大于前一个值时便进行利润计算,再把一个个小片段进行累加,得到最终结果。- 只要有利润,我们就要,这便是
局部最优
,把每个小利润加起来得到的最大值,便是全局最优
。
代码实现
1 | class Solution { |