题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

实例：

输入: [7,1,5,3,6,4]
输出: 7
解释:** 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

贪心算法(greedy algorithm)

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

贪心算法的步骤：

  1. 建立数学模型描述问题
  2. 将问题分解成若干的子问题
  3. 对子问题求解
  4. 将子问题的解归并成原问题的解。

贪心算法的使用条件：

  1. 贪心选择性质： 一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。


  1. 最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析

贪心算法的问题：

  1. 不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑
  2. 贪心算法一般用来解决求最大或最小解
  3. 贪心算法只能确定某些问题的可行性范围

题解

image.png
如图所示，我们只要求得所有上涨区间的值，就是我们这支股票的总利润。假设股票在a-d区间内一直上涨，那么他的利润就是 (b - a) + (c - b) + (d - c) = d - a 。我们将这个区间缩小到两天，那么我们只需要用后一天的价格减去前一天的价格，假如结果是正数，那么就是我们股票利润。

股票价格：[7,1,5,3,6,4]
利润：[-6, 4, -2, 3, -2]

去掉小于0数字，我们最终利润为7。

  1. export default function maxProfit(prices) {
  2.   let profit = 0
  3.   for (let i = 0; i < prices.length - 1; i++) {
  4.     const balance = prices[i + 1] - prices[i]
  5.     if (balance > 0) profit += balance
  6.   }
  7.   return profit
  8. }

这个问题的贪心策略比较简单，我们将整个问题简化成了两天中股票价格是否上升。并且最终所有上升的利润之和恰好是我们的总利润。