少女祈祷中...

题目

给定一个数组,它的第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
2
3
4
5
6
7
8
9
10
11
class Solution {
public int maxProfit(int[] prices) {
//作为返回值,统计结果
int result = 0;
for (int i = 1; i < prices.length; i++) {
//当前股票值高于前一天,即差值大于0,则加入利润中
result += Math.max(prices[i] - prices[i - 1], 0);
}
return result;
}
}