I find this by far the easiest solution as it's intuitive and is very close logically to the Brute Force method.

Kandane's works by having two variables indicating the current_max, and global_max each initialized to the 0th position of the starting array. As we iterate from 1..i..(n - 1) elements we indicate the maximum sub-array for the previous i positions with current_max. There can be only two possibilities either the maximum sub-array at position i is A[i] i.e. the maximum sub-array is that and only that position in the array. Or, there is some M (max) elements before A[i], plus the newly discovered A[i], this contains the maximal sub-array so far. If the A[i]th element is greater than our current maximum then we know it's part of maximal subarray, otherwise our global sum contains the max subarray so far.

An example:

[-2, 3, 2, -1]

i : 0 ->

(Curr Max and Global Max are initialized)

curr_max = A[0] = -2

global_max = A[0] = -2

i : 1 ->

(

curr_max = max(A[i], curr_max + A[i]) = max(3, (-2 + 3)) = 3

3 > -2 so update global_max

global_max = 3

i : 2 ->

curr_max = max(A[i], curr_max + A[i]) = max(2, (3 + 2)) = 5

5 > 3 so update global_max

global_max = 5

i : 3 ->

curr_max = max(A[i], curr_max + A[i]) = max(-1, ((5 + -1)) = 4

4 < 5

Continue

We reach the end of the array so return our global_max which is 5 tadah!

Code:

int maxSubArray(vector<int>& nums)

{

int global_max = nums[0], curr_max = nums[0];

for(int i = 1; i < nums.size(); ++i)

{

curr_max = max(nums[i], curr_max + nums[i]);

if(curr_max > global_max)

global_max = curr_max;

}

return global_max;

}