Javascript function that finds largest subarray

Question

I want to write a function that determines the largest sum that can be formed by any contiguous subarray in the array.

Input: [-2, 5, -1, 7, -3]
Output: 11 //because of subarray [5, -1, 7]

Input: [1, 2, -10, 20, 1]
Output: 21 //because of [20, 1]

My try

function Max (array) {

  let result = Math.max(...array);            //in case that there is only one pos. number or all neg.

  for (let i = 0; i<array.length; i++) {
    for (let j=0; j<array.length; j++) {

      if (array.reduce((array[i], array[j]) => array[i], array[j]))
      > result)
      
      {result = array.reduce((array[i], array[j]) => array[i], array[j]));
      }
    }
      array.shift[array[i]];
      array.pop[array[i]];
    }
  return result
  
}

My idea was the following:

Input [1, 2, 3, 4, -5]
       --->
       ----->
       -------->
       -------------> //check each of the 4 sums against the result

      [2, 3, 4, -5, 1]
       --->
       ----->
       -------->
       -------------> //check each of the 4 sums against the result

      [3, 4, -5, 1, 2]
       --->
       ----->
       -------->
       -------------> //check each of the 4 sums against the result

The basic idea should be correct, yet I couldn't correctly implement it in code. Thanks to everyone reading this or even helping a beginner out!

Answer 1

An alternative solution that I can think with O(n) complexity is:

var array = [-2,1,-3,4,-1,2,1,-5,4];

function maxSumSub(arr){
        let curr_sum=arr[0];
            let global_sum=arr[0];
            
            for (let i = 1; i < arr.length; i++) {
                
                if(arr[i]>curr_sum+arr[i]) {
                    curr_sum=arr[i];
                }else {
                    curr_sum=curr_sum+arr[i];
                }
                
                if(curr_sum>global_sum) {
                    global_sum=curr_sum;
                }
            }
    console.log(global_sum);
    }
  maxSumSub(array);

Answer 2

Working Code !!

const getMax = (data) => {
  let tempArr = [], resultArr = [];
  for (let i = 0; i < data.length; i++) {
    tempArr = [data[i]];
    for (let j = i + 1; j < data.length; j++) {
      tempArr.push(tempArr[tempArr.length - 1] + data[j]);
    }
    resultArr.push(Math.max(...tempArr));
  }
  return Math.max(...resultArr);
}

console.log(getMax([-2, 5, -1, 7, -3]));
console.log(getMax([1, 2, -10, 20, 1]));

Answer 3

Function to return both the max value and the array.

In the following algorithm, the first half runs through all linear combinations via 3 nested loops. It records the each element combinations against the sum.

The second half simply get the max value and return the array.

let a1 = [-2, 5, -1, 7, -3];

console.log(getMaxSumArray(a1));

function getMaxSumArray(a) {

  let allSums = [];
  
  //Select the start
  for (let start = 0; start <= a.length - 2; start++)
  
    //Select the end
    for (let end = start + 1; end <= a.length - 1; end++){
     
      //Do sum from start to end
      strArr = '[';
      sum = 0;
      for (let index = start; index <= end; index++){
        
        strArr += a[index] + (index < end ? ',' : '');
        sum += a[index];
        
      }
      
      strArr += ']';
      allSums.push({strArr, sum})
    }          
      

    //Find the max object    
    let maxObj = allSums.reduce((a, c) => {
    
      if (a.sum < c.sum)
        return c;
       else
        return a;
        
    }, {sum: 0})
  

    return maxObj;
}