题目描述

给定一个数组,它的第 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/
pwrliang Algorithms, Array, Dynamic Programming ,

Leave a Reply

Your email address will not be published. Required fields are marked *