My python solution with explanation

  • 0
    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[0]
            max_so_far      = A[0]
            # We initialize both of these variables to A[0] - the first element of the array.
            for x in A[1:]:
                #starting from the second element , A[1]
                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" .

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.