Maximum Subarray (Kadane’s algorithm approach)

https://leetcode.com/problems/maximum-subarray/description/

Input test case:

• [-2,1,-3,4,-1,2,1,-5,4]
• [-2, -1]
• [-2, 1]
• [1]
• [1, 2]

     function maxSubarray(array) {
          
            var currentMax = array[0];
            var max = array[0];
          
            for (var i = 0; i < array.length; i++) {
              // Compare 0 and currentMax + array[i]
              // IF it is less than 0, it is going to be 0 (Reset)
              //    it is more than 0, it will be currentMax + next element
              currentMax = Math.max(array[i], currentMax + array[i]);
            
              // Compare max or currentMax value, pick up one.
              max = Math.max(max, currentMax);
              
            }
          
            // Return max at the end of loop
            return max;
        }
    
    console.log(maxSubarray([-2,1,-3,4,-1,2,1,-5,4])) // === 6
    console.log(maxSubarray([-2, -1])) // === -1
    console.log(maxSubarray([-2,1])) // === 1
    console.log(maxSubarray([1])) // === 1
    console.log(maxSubarray([1, 2])) // === 3

I wanted to pass this case Input: [-2, -1] so that I modified var currentMax = 0; and var max = 0; to current code.

Apparently, Kadane’s algorithm is needed to include at least one positive number so that second case might not be solved by this.

Is it possible to solve all these test cases by using Kadane’s algorithm or do I need to implement in other ways?

Thanks!

Answer

var maxSubArray = function(nums) {
  let maxn = Number.MIN_VALUE; // Or Number.MIN_SAFE_INTEGER
  let sum = 0;

  nums.forEach(function(item, index, array) {
    sum += item;

    if (sum > maxn)
      maxn = sum;

    if (sum < 0)
      sum = 0;
  });

  return maxn;
};


console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])) // === 6
console.log(maxSubArray([-2, -1])) // === -1
console.log(maxSubArray([-2,1])) // === 1
console.log(maxSubArray([1])) // === 1
console.log(maxSubArray([1, 2])) // === 3