Javascript function that finds largest subarray [duplicate]

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!

Isn't there a lot of processing in the method you are following — Harmandeep Singh Kalsi
– Harmandeep Singh Kalsi, Commented Jul 4, 2020 at 14:05
this is an exact dupe. it's some kind of interview question thing — user120242
– user120242, Commented Jul 4, 2020 at 14:09
Whats come to top of my mind as solution is Brute Force Algorithm, i.e. you should check all the contiguous sub Arrays that can be derived from given Array...freecodecamp.org/news/brute-force-algorithms-explained — Manoj
– Manoj, Commented Jul 4, 2020 at 14:11

Harmandeep Singh Kalsi · Accepted Answer · 2020-07-04 14:11:56Z

3

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);

edited Jul 4, 2020 at 14:11

answered Jul 4, 2020 at 14:06

Harmandeep Singh Kalsi

3,3652 gold badges17 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Jenny Over a year ago

thank you, I was really amazed, that you can solve it with such elegant simplicity!

Charlie Over a year ago

Then you should upvote this nice answer

Jenny Over a year ago

@ Charlie, thanks for reminding me. thanks for your answer as well, just looking at it.

Harmandeep Singh Kalsi Over a year ago

Good to hear that it helped you @Jenny. Happy Learning!

Charlie · Accepted Answer · 2020-07-04 14:35:37Z

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;
}

solanki... · Accepted Answer · 2020-07-04 14:26:36Z

0

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]));

edited Jul 4, 2020 at 14:26

answered Jul 4, 2020 at 14:20

solanki...

5,1182 gold badges29 silver badges29 bronze badges

Collectives™ on Stack Overflow

Javascript function that finds largest subarray [duplicate]

3 Answers 3

4 Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Linked

Related