LeetCode.121.Best Time to Buy and Sell Stock 买卖股票的最佳时机

题目描述

121 Best Time to Buy and Sell Stock
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

---

解题过程

这道题求的就是数组元素的前后最大差值，就是找 i,j, i < j，使得 prices[j] - prices[i] 最大

维持两个变量， min 表示目前为止的最小值， maxDiff 表示当前值与最小值差值的最大值
则一次遍历后 maxDiff 就是最大利润

说这道题是 动态规划，但不那么明显，状态转移方程可以写为
前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

时间复杂度 O(n) 空间复杂度 O(1)

还看了另一个解法，思想是： 原数组两个元素的最大差等于求差数组的最大子序和

private static class SolutionV2020 {
    public int maxProfit(int[] prices) {
        if (null == prices || prices.length == 0) {
            return 0;
        }
        int min = prices[0];
        // 当前值与最小值差值的最大值
        int maxDiff = 0;

        for (int n : prices) {
            min = Math.min(min, n);
            maxDiff = Math.max(maxDiff, n - min);
        }
        return maxDiff;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_121_BestTimeToBuyAndSellStock.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_121_BestTimeToBuyAndSellStock.java

---