class Solution: # @param A, a list of integers # @return an integer def maxSubArray(self, A): # this is best solved using Kadane's algorithm # we need two variables to solve this - # --- (1) max ending here - this keeps track of the largest subbarray sum till that particular index # --- (2) max so far - this keeps track of the largest sum of all sub arrays parsed so far. max_ending_here = A max_so_far = A # We initialize both of these variables to A - the first element of the array. for x in A[1:]: #starting from the second element , A max_ending_here = max(x, max_ending_here+x) max_so_far = max(max_so_far,max_ending_here) return max_so_far
So, I spent a while trying to understand this algorithm - thought I would share them with everyone. The problem is solved using an algorithm called Kadane's algorithm. If you have tried to solve this problem with out googling & decided to take a look at the discussions here ; don't worry - this is not a straightforward problem to solve ( the problem was originally proposed in 1977 and the solution came along only in 1984) , the Computer Science fraternity fairly scratched their head before developing this algorithm.
==> The idea is to have two tracking variables ;
(1) max ending here - for any element in the array , a[i] , max_ending_here keeps track of the "largest sum" of all sub-arrays , that the array could have till a[i] (2) max_so_far - keeps track of the "largest sum" seen so far in the array , it doesnt necessarily have to be the most recent "max_ending_here" .