⏱ 0:02est. 3 min

Largest Sum Contiguous Subarray

// https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
let arr = [-2, -3, 4, -1, -2, 1, 5, -3]

function findMax() {
    let max_so_far = 0, max_ending_here =0;
    for(let i=0; i<arr.length;i++) {
        max_ending_here += arr[i];

        if (max_so_far<max_ending_here) {
            max_so_far = max_ending_here;
        }
        if(max_ending_here<0) {
            max_ending_here=0;
        }
    }

    return max_so_far;
}

console.log(findMax())