LI@NG

Leetcode 121 Best time to buy and sell stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

动态规划

关键点在于profit,最终的最优解,即为在每步最优解中取最优解

建立一个profits数组存储每天最优解,最终选择最优解,当然这里要时刻跟踪最小值。

var maxProfit = function(prices) {
	var profits = [];
	var minPrice = prices[0];
	for (let i = 0; i < prices.length; i++) {
		minPrice = Math.min(minPrice, prices[i]);
		profits[i] = prices[i] - minPrice;
	}
	return Math.max(...profits);
};

优化后:

var maxProfit = function(prices) {
    var minPrice = Number.MAX_VALUE, maxProfit = 0;

    for (var i = 0; i < prices.length; i++) {
    	minPrice = Math.min(minPrice, prices[i]);
    	var profit = prices[i] - minPrice;
    	maxProfit = Math.max(maxProfit, profit);
    }

    return maxProfit;
};