Maximum Subarray Sum Solution in JavaScript
When encounter the problem about finding the largest sum of contiguous subarray within an array, the optimized solution for now is Kandane’s algorithm. To understand the Kandane’s algorithm, first we need to learn about dynamic programming.
Dynamic programming is a problem solving method for solving an optimization problem by breaking it down into simpler sub-problems. Don’t get intimidated by the theory, it is mostly just a matter of taking a recursive algorithm and finding the overlapping sub-problems. One of the simplest examples of dynamic programming is the classic nth Fibonacci number. There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems.
Dynamic programming has two methodologies: top-down & bottom-up. Top-down approach starts to solve the bigger problem by recursively finding the solution to smaller sub-problems. While dealing with the sub-problems, we cache those results for future recursive calls. This way of storing the results of already solved sub-problems is called memoization. Contrary to memoization, bottom-up approach starts to solve the subproblems first, and iteratively generating solutions to bigger and bigger sub-problems by using the solutions to small sub-problems. The way to cumulating answers to the top is called tabulation.
How Kandane’s algorithm falls under dynamic programming paradigm? Let’s see an example(link).
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
With Kandane’s algorithm we search the given array nums[1…n] from left to right. In the ith step, it calculate the subarray with the largest sum ending at i, this sum is maintained in currentSum. Moreover, it calculates the subarray with the largest sum anywhere in nums[1…n], maintained in maxSum and easily obtained as the maximum of all values of currentSum.
The Kandane’s algorithm uses optimal substructures and overlapping sub-problems with bottom-up approach by tabulation. Because we loop through the array once, the time complexity is O(n).
To understand the solution better, you can test it out with this repl link.
Next time, I hope you could use Kandane’s algorithm to solve similar problems. ;)
Resources:
