题目描述

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

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

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

示例 1:

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

示例 2:

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

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

解法1

解法1使用动态规划方法，我们定义两个数组L和P。L[i]表示第0…i天最低的股价；P[i]表示第0…i天能获得的最大利益，那么答案 = max(P[i]), 1 <= i < |prices|。

那么我们就能够写出状态转移方程L[i] = min(L[i] – 1, prices[i]), P[i] = max(P[i – 1], prices[i] – L[i]), 1 <= i < |prices|. 根据状态转移方程，我们能够写出如下代码。

import java.util.Arrays;

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0)
            return 0;
        // L[i] 第i天及以前最低股价
        // P[i] 第i天能获得的最大利益
        int[] L = new int[prices.length];

        L[0] = prices[0];

        for (int i = 1; i < prices.length; i++) {
            L[i] = Math.min(L[i - 1], prices[i]);
        }

        int[] P = new int[prices.length];

        for (int i = 1; i < prices.length; i++) {
            P[i] = Math.max(P[i - 1], prices[i] - L[i]);
        }

        return Arrays.stream(P).max().getAsInt();
    }
}

解法2

我们通过观察例子“[7,1,5,3,6,4]”，为了最大利益我们可以选择在股价历史中的最低点买入，最高点卖出。在这个例子中，我们选择prices[1] = 1时买入， 在prices[4] = 6时卖出，能获得最大利益5.

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;

        int lowestPrice = prices[0];
        int res = 0;

        for (int i = 1; i < prices.length; i++) {
            res = Math.max(res, prices[i] - lowestPrice);
            lowestPrice = Math.min(lowestPrice, prices[i]);
        }

        return res;
    }
}

解法3

解法3首先求得每一天的profit，然后求出连续多天交易产生的最大的profit。例如prices = [7, 1, 5, 3, 6, 4]，profit = [ ,-6,4,-2,3,-2]。4-2+3能产生最大的profit = 5，就是最终的答案。

我们分析下为什么这么做是正确的，prices[3] = 3，prices[4] = 6，我们能获得3的收益；prices[2]=5, prices[1]=1我们能获得4的收益。但为了在i=3买入，我们需要在i=2卖出，这就导致了我们在i=2 到 i=3这笔交易产生了-2的损失。我们要扣去这次的损失，所以我们求得连续最大和就是答案。在这个case中使用这种方法，物理意义上产生了3次交易，而解法1与2只产生了一次交易。

class Solution {
    public int maxProfit(int[] prices) {
        int[] profit = new int[prices.length];

        for (int i = 1; i < prices.length; i++) {
            profit[i] = prices[i] - prices[i - 1];
        }

        int maxSum = 0;
        int res = 0;
        for (int i = 1; i < profit.length; i++) {
            maxSum += profit[i];
            res = Math.max(res, maxSum);

            if (maxSum < 0)
                maxSum = 0;
        }
        return res;
    }
}

参考：

1. https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-121-best-time-to-buy-and-sell-stock/