[Leetcode] Maximum Subarray

Problem

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Algorithm 

This is the Largest Continuous Subarray (LCS) problem. The brute force solution has a O(n^2) running time. 

Divide-and-Conquer

The LCS can be found in the left subarray, the right subarray, or cross the middle point. Crossing the middle point, we can scan from middle to left end and right end of the array, computing the left and right largest continuous sum. 

Linear Algorithm
Claim: The Largest Continuous Subarray can be divided into two subarrays, the sum of each is positive.
Proof: If one subarray is negative, we can delete it from the LCS, and the remaining part should be the LCS.

We can use a variable to track the continuous sum. Whenever it drops below zero, we reset it to be zero. 

Code