Maximum Subarray (Kadane's algorithm approach)

Question

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 1

Largest Sum Contiguous Subarray.

Here is my solutions to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

i written this code without following any algorithm.

function lrgSumContiArr(arr) {
  function getSum(startIndex, endIdex){
    return arr.slice(startIndex, endIdex).reduce((acc, cur) => acc + cur);
  }
  const lrgSumArrOfSubArr = arr.map((item, index) =>{
    let largeSum = Number.NEGATIVE_INFINITY;
    for(let i=index; i<arr.length; i++) {
        let subArrSum = getSum(index,i+1);
        if( subArrSum > largeSum) {
        largeSum = subArrSum;
      }
    }
    return largeSum;
  });
  /* const lrgSumOfSubArr = lrgSumArrOfSubArr.reduce((acc, cur) => {
    if (acc > cur){
      return acc;
    } else {
      return cur;
    }
  });
  return lrgSumOfSubArr; */
  return Math.max.apply(null,lrgSumArrOfSubArr);
}
lrgSumContiArr([-2,-3,4,-1,-2,1,5,2]);

Answer 2

function maxSubarray(a) {
    var l=a.length;

    if (!l) {
        return;
    }

    var ps, ms;
    ps=ms=a[0];

    for(var i=1; i<l; i++) {
        ps=Math.max(a[i],ps+a[i]);
        ms=Math.max(ms,ps);
    }

    return ms;
}

Answer 3

Just saw this, It will find the sum of max sub array

public class MaxSubArray{
static void sumM(int a[], int n){
    int s1 = Integer.MAX_VALUE;
    int k = Integer.MAX_VALUE;
    int sum = 0;
    int s2 = 0;
    for(int i=0;i<n;i++){

        if(a[i]<s1){
            if(a[i]<0){
                k = Math.min(a[i],s1);
            }
        }

        if(a[i]>k){
            sum+=a[i];
        }

        if(a[i]<k){
            if(a[i]<0){
                continue;
                
            }
            s2+=a[i];
        }

    }
        if(sum>s2){
            System.out.println(sum);
        }
        else{
            System.out.println(s2);
        }
    
     
}

    public static void main(String[] args){
        int a[] = {1,2,3,-7,4,5};

        int n = a.length;

        sumM(a,n);
    }

    
}

Answer 4

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