题目内容

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

解法一，暴力法

思路很简单，即是用两层循环将所有可能的交易算一遍，挨个比较每次交易的利润。每次比较都更新当前最大的利润（如果是的话），到最后即可得出给定周期内的最大利润。

var maxProfit = function(prices) {
    let index = 0
    let temp
    for (let m = 0; m< prices.length;m++) {
        for (n = m + 1; n < prices.length;n++) {
            temp = prices[n] - prices[m] 
            if (temp > index) {
                index = temp
            }
        }
    }
    return index
};

解法二，动态历史低指比较法

这个方法不是自己想出来的，是从题解区官方解法看到的。一开始还领会错了意思，我以为是用min方法找到最低值，然后一次循环找到最大利润。虽然现实生活中都想抄底，但题中由于是给定价格周期，且最低点后面的价格可能仍然较低，所以不一定买在低点就意味着最大盈利。以[7,2,8,0,1]为例，这里1是最低点，但如果以此计算利润的话只有1，而在2价买入8价卖出的话，利润有6。

所以这里有个思维上的误区，尽管简单（但我还是开心地跳进去了=_=）。

错误代码

var maxProfit = function(prices) {
    let minVal = Math.min(...prices)
    let minIndex = prices.indexOf(minVal)
    if (minIndex === prices.length - 1) {
        // 处理地点在末尾的情况
        prices.pop()
        minVal = Math.min(...prices)
        minIndex = prices.indexOf(minVal)
    }
    
    let temp  = 0
    for(let i = minIndex; i < prices.length; i ++) {
        if ((prices[i] - minVal) > temp) {
            temp = prices[i] - minVal
        }
    }
    return temp
};

正确的思路应该是，历史最低点应该是动态的值，应该比较每个卖点与历史最低点的利润来得到最大利润。

假定当前项是历史最低点，计算此历史最低点与其后的卖点利润，直到下一次历史最低点出现再计算。

正确代码

var maxProfit = function(prices) {
    let valley = Number.MAX_SAFE_INTEGER;
    let max = 0;
    for(var i = 0;i < prices.length;i++){
        if(prices[i] < valley){
            valley = prices[i];
        }else{
            max = Math.max(max,prices[i] - valley);
        }
    }
    return max;
};