# My python solution with explanation

• ``````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" .``````

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