010.md

买股票问题

问题描述

给定一数组，第i个元素代表第i天股票的估价，假设最多允许买卖一次，求最大利润（股票的利润为卖出价-买进价）。

问题规约

等价于求max(ary[j]-ary[i]),其中i<j，j,i取遍所有可取的值。 JS实现

function maxProfit(ary,low,high) {
    // body...
    var length = high-low+1;
    if (length <= 1) {return 0;}
    var max_profit = 0,
        min = low;
    for (let i = 1; i < length; i++) {
        if (ary[i] > ary[min]) {
            max_profit = Math.max(max_profit,ary[i]-ary[min]);
        }else if(ary[i] < ary[min]){
            min = i;
        }
    }
    return max_profit;
}

注：

1、只扫描一遍数组，同时用一个辅助变量min记录其最小值下标，如果当前值ary[i]小于ary[min],则只更新最最小值的下标，（因为无论在之前的何处买进股票），在该处卖出股票不可能得到利润，如果当前值ary[i]大于ary[min],则在该处卖出利润必定能得到利润，决策后取最大利润。