Given an array, find the greatest sum of a contiguous subset. For example, the input can be [3, 5, -9, 1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, 4] and the output should be 19 because the contiguous subset with the greatest sum is [1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1]
So conceptually, what’s the best approach to solving this problem? We need to create a function that iterates through each individual element and holds both the current running total as well as the overall maximum running total. Let’s call the current running total maxEndingHere
and the overall max maxSoFar
. In order to maximize…