Web前端面试真题（算法篇）：005篇

股票最大利润
假设有一个数组, 它的第i个元素对应第i天的价格
最多只允许完成一次交易(买进一次,卖出一次)
设计一个算法找出最大利润
例如: [7,1,5,3,6,4] 最大利润 5

function maxIncome(prices) {
    var 收益值 = 0; 
    var 买入时间 = 0;
    var 最大收益 = 0;
    for(var i = 1; i < prices.length; i++) {
        //假设我们从第一天买入，收益为0， 循环从1开始，第二天计算收益
                                
        //当前收益值
        收益值 = prices[i]-prices[买入时间]; 
                
        //若当前收益出现负数或0，则意味着有比买入价更低的价格出现
        //我们开始计算下一个买入时间点
        if(收益值<=0) 买入时间=i;
                                
        //每次都将更大的收益保留
        //若没有出现更大的收益，则不做更新
        //最终，最大收益会被保留下来
        if(收益值>=最大收益) 最大收益=收益值;
                                
        /*
        唯一不足之处，是不太容易记录买入和卖出时机。
        */
    }
    return 最大收益;
}
console.log( maxIncome([7,1,5,3,6,4]) );

如果这个计算方法你不是非常能理解, 我们再来换一个简单一点的思路

function maxIncome(prices) {
    var 最大收益 = 0;
    for(var i = 0; i < prices.length-1; i++) {
        for(var j = i+1; j < prices.length; j++) {
            //就是穷举每个买入及卖出的差价
            var 收益值 = prices[j] - prices[i];
            if(收益值>=最大收益) 最大收益 = 收益值;
        }
    }
    return 最大收益;
}
console.log( maxIncome([7,1,5,3,6,4]) );

这个思路虽然简单, 但浪费了很多计算次数
优化改良之后, 就是开头的版本了