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

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

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

个人认为的注意点：最多允许完成一次交易

示例一：

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

示例二：

输入： [7, 6, 4, 3, 1]
输出： 0
解释：没有交易，最大利润就是0

解题思路 0 ——暴力法

维护一个maxProfit变量，遍历数组中的每一项，然后跟该项后面的项进行利润比较，如果利润大于当前的最大利润，则更新之

时间复杂度： O(n^2)

空间复杂度：O(1)

编码实现

function maxProfit (arr) {
    var maxProfit = 0
    for (var i = 0; i < arr.length; ++i) {
        for (var j = i+1; j < arr.length; ++j) {
            if (arr[j] - arr[i] > maxProfit) {
                maxProfit = arr[j] - arr[i]
            }
        }
    }
    return maxProfit
}

解题思路1：一次遍历法：

维护两个变量：maxProfit （初值为0）和 minprice （初值为无限大） ，然后遍历数组，如果当前项小于我们维护的最小值，则更新最小值为当前项的值，然后，判断当前项减去最小值是否大于maxProfit，如果大于，则更新之

编码实现

function maxProfit (arr) {
    let maxProfit = 0, minPrice = Infinity
    arr.forEach((item) => {
        if (item < minPrice) {
            minPrice = item
        }
        if (item - minPrice > maxProfit) {
            maxProfit = item - minPrice
        }
    })
}

解题思路2：一次遍历

维护两个变量，一个是当前的利润值currentProfit，一个是最高的利润值maxProfit

遍历数组，当前利润加上用后一项的值减去当前值的值 ，如果当前利润值小于零，我们则将当前利润值归零。否则，不作处理。下一步，如果当前利润值大于最高的利润值，则更新最高利润值为当前值

编码实现：

function maxProfit (arr) {
    let currentProfit = 0, maxProfit = 0
    for (let i = 0; i < arr.length - 1; ++i) {
        currentProfit += arr[i+1] - arr[i]
        if (currentProfit < 0) {
            currentProfit = 0
        }
        if (currentProfit > maxProfit) {
            maxProfit = currentProfit
        }
    }
}