[剑指 Offer 第 2 版第 63 题] “股票的最大利润”做题记录

第 63 题：股票的最大利润

传送门：股票的最大利润 。

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖交易该股票可能获得的利润是多少？

例如一只股票在某些时间节点的价格为 [9, 11, 8, 5, 7, 12, 16, 14]。

如果我们能在价格为 5 的时候买入并在价格为 16 时卖出，则能收获最大的利润 11。

样例：

输入：[9, 11, 8, 5, 7, 12, 16, 14]

输出：11

思路：在过往的股价中找到最低价，“当前股价 – 最低价”为获利。遍历过程中，找到这个获利的最大值即可。由于只允许做一次股票买卖交易，枚举每一天作为卖出的日子，买入日子一定在卖出日子之前，为了获利最多，希望买入的日子的股票价格尽可能低。用 minnum 记录第 0 到 第 i 天的最低价格，则在第 i 天卖出的最大获利为 nums[i] - minnum，枚举 i 找到最大获利。

Python 代码：

  class Solution(object):
        def maxDiff(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            l = len(nums)
            if l == 0:
                return 0

            min_val = nums[0]
            max_profit = 0
            for i in range(1, l):
                min_val = min(min_val, nums[i])
                max_profit = max(max_profit, nums[i] - min_val)
            return max_profit

同 LeetCode 第 121 题。

传送门：121. 买卖股票的最佳时机。

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

Java 代码：

  public class Solution2 {

        // 留意这个解法的语义

        public int maxProfit(int[] prices) {
            int buy = Integer.MIN_VALUE;
            int sell = 0;
            for (int price : prices) {
                // 在当前以及之前如果执行了买操作，能够得到的利润的最大值
                buy = Math.max(buy, -price);
                // 在当前以及之前如果执行了卖操作，能够得到的利润的最大值
                sell = Math.max(sell, buy + price);
            }
            return sell;
        }

        public static void main(String[] args) {
            int[] prices = {7, 1, 5, 3, 6, 4};
            Solution2 solution2 = new Solution2();
            int maxProfit = solution2.maxProfit(prices);
            System.out.println(maxProfit);
        }
    }

区别于 LeetCode 第 122 题。

传送门： 122. 买卖股票的最佳时机 II。

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

参考资料：从零开始学贪心算法 – CSDN博客 https://blog.csdn.net/qq_32400847/article/details/51336300

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/