剑指 Offer 63. 股票的最大利润

题目

题目链接

https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/

解题思路

题解

动态规划

1. 利润计算：加入第 a 天买入，第 b 天卖出，利润为 prices[b] - price[a]，且 b > a
2. 此时假设，第 a 天的价格是这几天中最低的，且假设第 b 天为这几天中最高价，此时 prices[b] - price[a] 就为最大利润
3. 此时在 2 的基础上，假如今天是第 c 天，此时最大利润：Math.max(price[c], price[b] - price[a])

代码

class Solution {

    public int maxProfit(int[] prices) {
        // 最大利润
        int maxProfit = 0;
        // 最小价格
        int minPrice = 0;
        for (int i = 0; i < prices.length; i++) {
            // 刚开始不存在所谓的利润，此时第一日就为最小价格
            if (i == 0) {
                minPrice = prices[i];
                continue;
            }
            // 今天加个比最小的还小，替换最小值
            if (prices[i] < minPrice) {
                minPrice = prices[i];
                continue;
            }
            // 最大利润：今天加个 - 最小价格 与 已经计算过的最大差价比较，去更大的那个
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
        return maxProfit;
    }
}