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