1, 题目

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

  1. 输入: [7,1,5,3,6,4]
  2. 输出: 5
  3. 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
  4.     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:

  1. 输入: [7,6,4,3,1]
  2. 输出: 0
  3. 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

1, 动态规划

  1. 定义问题:
  2.     fn是第n天卖出所得的利润,可得状态转义方程
  1. #scala
  2. object Solution {
  3.     def maxProfit(prices: Array[Int]): Int = {
  4.         if (prices.length == 0) {
  5.             return 0
  6.         }
  7.         var max_profit = 0
  8.         var fn = 0
  9.         for (i <- 1 until prices.length) {
  10.             val profit = prices(i) - prices(i - 1)
  11.             if (fn == 0) {
  12.                 fn = 0.max(profit)
  13.             } else {
  14.                 fn = 0.max(fn + profit)
  15.             }
  16.             max_profit = max_profit.max(fn)
  17.         }
  18.         max_profit
  19.     }
  20. }
  1. #scala变形
  2. object Solution {
  3.     def maxProfit(prices: Array[Int]): Int = {
  4.         if (prices.length == 0) {
  5.             return 0
  6.         }
  7.         var max_profit = 0
  8.         var fn = 0
  9.         for (i <- 1 until prices.length) {
  10.             val profit = prices(i) - prices(i - 1)
  11.             fn = 0.max(fn + profit)
  12.             max_profit = max_profit.max(fn)
  13.         }
  14.         max_profit
  15.     }
  16. }
  1. #python变形
  2. class Solution:
  3.     def maxProfit(self, prices: List[int]) -> int:
  4.         if prices:
  5.             fn = 0
  6.             max_profit = 0
  7.             for i in range(1, len(prices)):
  8.                 profit = prices[i] - prices[i - 1]
  9.                 fn = max(0, fn + profit)
  10.                 max_profit = max(max_profit, fn)
  11.             return max_profit
  12.         else:
  13.             return 0

2, 此问题等价最大子序和

最大子序和