贪心算法

题目

给定一个数组，它的第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;
    }
}