股票的最大利润

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

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

0 <= 数组长度 <= 10^5

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
    public int maxProfit(int[] prices) {

        // 边界判断，如果交易日为 0 天，那么没得交易，返回 0
        // 如果交易日为 1 天，只能当天买当天卖，利润为 0
        if( prices.length < 2 ) return 0;

        // 设置 dp 数组，用来存放每天的最大利润
        // dp[i] 表示以 prices[i] 为结尾的最大利润
        // dp[0] 表示以 prices[0] 为结尾的最大利润
        // dp[1] 表示以 prices[1] 为结尾的最大利润
        int[] dp = new int[prices.length];

        // dp[0] 表示以 prices[0] 为结尾的最大利润
        // 由于只有一个交易日，只能当天买当天卖，利润为 0
        dp[0] = 0;

        // 初始化变量 buy，表示在哪一天购买股票
        // 一开始在第 0 天购买
        int buy = prices[0];

        // 通过 for 循环，填充 dp
        for(int i = 1 ; i < prices.length ; i++){
            
            // 获取此时的股票价格
            int sell = prices[i];
            
            // 如果在这一天卖出去，那么利润就是当天的股票价格减去之前的购买价格
            int profit = sell - buy;

            // 对比一下，哪个利润更大
            dp[i] = Math.max(dp[ i - 1] ,profit);

            // 更新变量 buy，让 buy 为当前区间里的最小值
            buy = Math.min(buy,prices[i]);

        }

        // 返回 dp 的最后一个结果就行
        return dp[prices.length - 1];

    }
}