SOURCE

//暴力解法
function maxSubSeqSum(sequence){
    let maxSum = 0
    let len = sequence.length
    for(let i = 0;i < len;i++){
        let thisSum = sequence[i]
        for(let j = i + 1;j < len;j++){
            thisSum += sequence[j]
            if(thisSum > maxSum){
                maxSum = thisSum
            }
        }
    }
    return maxSum
}

//获取最大值
function max(){
    //console.log(Array.prototype.slice.apply(arguments))
    let arr = Array.prototype.slice.apply(arguments).filter(a => a >= 0).sort((a, b) => b - a)
    return arr[0] ? arr[0] : 0
}

//分而治之解法
function maxSubSeqSum1(seq, left, right){//left包含 right不包含
    if(left + 1 == right) return 0
    //if(left + 2 == right) return seq[0] + seq[1]

    let middle = parseInt((right + left)/2)

    let leftMaxSum = maxSubSeqSum1(seq, left, middle)
    let rightMaxSum = maxSubSeqSum1(seq, middle, right)

    //左侧跨界取最大值
    let leftBorderMaxSum = 0, thisLeftBorderSum = 0
    for(let i = middle - 1;i >= left;i--){
        thisLeftBorderSum += seq[i]
        if(thisLeftBorderSum > leftBorderMaxSum)
            leftBorderMaxSum = thisLeftBorderSum               
    }
    
    //右侧跨界取最大值
    let rightBorderMaxSum = 0, thisRightBorderSum = 0
    for(let j = middle;j < right;j++){
        thisRightBorderSum += seq[j]
        if(thisRightBorderSum > rightBorderMaxSum)
            rightBorderMaxSum = thisRightBorderSum      
    }

    return max(leftMaxSum, rightMaxSum, leftBorderMaxSum + rightBorderMaxSum)
}

//let arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
//let arr = [-2, 1, -3]

let arr = [5, 4, -1, 6, 7]
console.log("暴力解法值", maxSubSeqSum(arr))
console.log("分而治之解法值", maxSubSeqSum1(arr, 0, arr.length))