Maximum Sub-Array (DP) problem

contiguous subarray means you have to pick elements from that array in sequential order. [7, -9] would be a contiguous sub array. [7, 2] would not. Array.slice() makes a contiguous sub-array.

If it doesnt say how long fo a sub array it wants im assuming you have to run through that array, make sub arrays of every length, get the sums of each and find which one has the largest sum if you were to add all the elements together.

If i have that definition right, then my naive solution would be something like

let arr = [7, -9, 2, 7, 4, -3, 1, -2, -7, 6, 9, 3, -9, -3, 4, -5, -10, 8, -5, 9, 9, -5, 9, 4, -5, 6, 5, -2, -2, -4, 8, -6, -10, 10, -1, -5, -10, 7, -7, 1, 4, -5, -4, 7, 4, 4, 5, 10, 1, -3]

const largestSubArray = function(array){
    let accumulator = []
    for (let start = 0; start < array.length; start++) {
        for (let end = start + 1; end < array.length; end++){
            let sum = array.slice(start, end).reduce((acc, cur) => acc + cur);
            accumulator[sum] = [start, end];
        }
    }

    let sum = accumulator.length-1;
    let [start, end] = accumulator[sum]
    let subArray = array.slice(start, end);

    console.log("sum", sum); //sum 40
    console.log("start", start, "end", end,); //start 17 end 49

    return subArray;
}

console.log(largestSubArray(arr))

i'm sure if we're worried about time/space complexity there's a better way to do it.

/r/learnjavascript Thread