LintCode冏的生意

约翰的生意
在一条数轴上，有n个城市，编号从0 ~ n – 1 , 约翰打算在这n个城市做点生意，他对Armani的一批货物感兴趣，每个城市对于这批货物都有一个价格prices[i]。对于城市x,约翰可从城市编号为[x - k, x + k]购买货物，然后卖到城市x,问约翰在每个城市最多能赚到多少钱？
样例
给出 prices = [1, 3, 2, 1, 5], k = 2,返回 [0, 2, 1, 0, 4]。

TLE暴力版：

// O(2 * n * k * log2k)
const business = function (A, k) {
    var result = [];
    for(var i = 0;i<A.length;i++){
        var start = i - k > 0? i-k:0;
        var minPrice = Math.min.apply(this,A.slice(start,i+k));
        var profit = Math.max((A[i] - minPrice),0);
        result.push(profit);
    }
    return result;
}

改进版，没有AC有WA，但是我没找到算法的问题，先写上来了：

// O(2n +2n * log2k)
const business = function (A, k) {
    var result = [];
    for(let i = 0;i<A.length;i+=k){
        let min = Math.min.apply(null,A.slice((i - k > 0? i-k:0),i+k));
        for(let j = -k;j<k;j++){
            if(j+i<0){
                j = -i;
            }else if(j+i>A.length){
                break;
            }
            if(!result[j+i] || !result[j+i]>=min){
                result[j+i]=min;
            }
        }
    }
    A.forEach((x,i)=>{
        A[i] = x-result[i];
    })
    return A;
}

在k>1的情况下
(1+log2k)<<(k * log2k)