Before we get to the algorithm, first let us understand what is a subarray. Consider the array-

a = [4,8,-3,10,-6]

A subarray is composed of the part of a given array, and it must be contagious, meaning that the indices are consecutive. So, the list of subarrys will be-

s1 = [4], s2 = [8], s3 = [-3], s4 = [10], s5 = [-6]

s6 = [4,8], s7 = [8,-3], s8 = [-3,10], s9 = [10,-6]

s10 = [4,8,-3], s11 = [8,-3,10], s12 = [-3,10,-6]

s13 = [4,8,-3,10], s14 = [8,-3,10,-6]

s15 = [4,8,-3,10,-6]

Now we want to answer which one of these 15 subarray have the maximum sum. If there were no negative numbers, the answer would have been simply the summation of all the numbers in the array. This is where Kadane’s algorithm comes to the rescue and provides an efficient solution to this problem in linear time!

Let’s start from first index, nums[0] = 4 , there is only one possible maximum sum which is 4.

Initially both our currentMax and maxSum is 4.

Moving to the next index, we have two choices [4],[4,8]

Summation of [4,8]= 12 and the maximum choice between [4] and [4,8] is [4,8] .

// At index 1
currentMax = max(8, 12) // max(valueAtIndex, currentMax + valueAtIndex)
maxSum = max(maxSum, currentMax) // 12
 
// At index 2
currentMax = max(-3, 12 + (-3)) // 12
maxSum = (12, 12) // 12

// At index 3
currentMax = max(10, 12 + 10) // 22
maxSum = max(12, 22) // 22

// At index 4
currentMax = max(-6, 22 + (-6)) // 16
maxSum = max(22, 16) // 22

Here is the code in JavaScript-

function maxSubArray(nums) {
    let maxSum = nums[0]
    let currentMax = nums[0]
    for(let idx = 1; idx < nums.length; idx += 1) {
      currentMax = Math.max(currentMax + nums[idx], nums[idx])
      maxSum = Math.max(currentMax, maxSum)
    }
    return maxSum
}