SOURCE

// 贪心算法：只要当前指针指到的元素之前的子数组和小于0，
// 就丢弃,从当前元素开始重新计算

// function findMax(arr) {
//     let pre = arr[0]; //之前的和
//     let sum = arr[0]; // 最大和
//     for(let i = 1; i < arr.length; i++) {
//         pre = Math.max(pre, 0) + arr[i];
//         sum = Math.max(pre, sum);
//     }
//     return sum;
// }

function findMax(arr) {
    let cur = arr[0]; // 当前的和
    let sum = arr[0]; // 最大和
    for(let i of arr) {
        cur = Math.max(cur, 0) + i;
        sum = Math.max(cur, sum);
    }
    return sum;
}

let arr = [1, -2, 3, 5, -2, 6, -1];
console.log(findMax(arr));

// 贪心算法那