[Java] Find largest sum subarray - Kadane's algorithm

Given an array of integers, the maximum subarray problem is about finding the subarray with the largest sum given the following specifications:

• for an array of all negative numbers, return the smallest of them
• for an array of all positive numbers, return the sum of all element

As output we want the start and end indexes as well as the total sum for the biggest portion identified. There may be multiple solutions.

The O(N) idea is to walk the array while keeping track of the local best and global best. The local best is the sum of elements until the one being currently considered; we initialize both to the first element of the array and remember to begin the loop from the element in position 1!

At each time, the local best can either be improved by adding to it the current element, or reset to start from the current element otherwise. We make this consideration first and in case, move the start index of the current best solution to the current position, then we compare it against the global maximum updating it if needed.

We track the result in an auxiliary structure, Range. You can check its implementation on my Gist alongside the implementation of getLargestSumSubarray and some test cases in LargestSumSubarrayJTests.

Turns out this algorithm is called Kadane's algorithm.