leetcode#121 买卖股票的最佳时机

审题

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

题目解析

从某一天开始买入直到某一天卖出，获得收益最大值，其中注意题目提示有可以不买入操作，这里我们使用小技巧 max = 0 标识不买入即可。

第一次

暴力方式首先验证解答思想是否正确。此方式明显复杂度较高。进一步解题可得知，我们仅需要在最小值买入最大值卖出即可，请查阅第二次解答。

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length; i++) {
            int buyPrice = prices[i];
            // 尝试卖掉
            for (int j = i + 1; j < prices.length; j++) {
                int got = prices[j] - buyPrice;
                if (got > max) {
                    max = got;
                }
            }
        }
        return max;
    }
}

第二次

通过不断记录最小买入值，进一次比较当日价格并判断是否大于最大收益（得到高点），如果整体价格呈下跌趋势那 max 变量将不会变化，也就是表达题目中不进行买入操作。

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int price = prices[i]; // 记做买入
        for (int i = 1; i < prices.length; i++) { 
           max = Math.max(max, prices[i] - price);
           price = Math.min(price,  prices[i])
        }
        return max;
    }
}