Given a one dimensional array of numbers ([1…n]), return the sum of a continuous subarray of numbers with the largest sum.
For example given the array: [−2, 1, −3, 4, −1, 2, 1, −5, 4] the continuous subarray with the largest sum is [4, −1, 2, 1], with a sum of 6.
My Initial Solution:
Optimizations:
This problem set can be solved via several different approaches including brute force, divide and conquer, and dynamic programming. A brute force solution would be a nested loop similar to last week’s initial solution. We iterate through array with an initial position and check all possible combinations and only update our max_so_far whenever a loop returns a higher sum.
O(n2) Time:
The most efficient solution is something called Kadane’s Algorithm which helps to break down the problem into smaller pieces but still following the same principal of collecting a “global” max sum (max_so_far), and a localized sum (max_ending_here) of the current iterative loop. This is part of a larger optimization principle called Dynamic Programming which relies on breaking problems down to smaller sub-problems, finding optimal solutions these sub-problems that will yield an optimal solution to the overall problem.
O(n) Time:
Since we know that the subarray has to be continuous we really only need one loop. We no longer need an array to collect our localized sum (max_ending_here) because we only use this value to calculate the next local max and only update the global max (max_so_far) when our subproblem (subarray) returns a higher value. Our max_so_far at the end of this loop by default will only be the highest value after the iterations.