Javascript 查找最大子数组的函数

Question

我想写一个函数来确定数组中任何连续子数组可以形成的最大和。

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]

我的尝试


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
  
}

我的想法如下：

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

基本思路应该是正确的，但是我无法在代码中正确实现。感谢所有阅读本文甚至帮助初学者的人！

Answer 1

我认为复杂度为 O(n) 的替代解决方案是：

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

工作代码!!

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

函数return最大值和数组。

在下面的算法中，前半部分通过3个嵌套循环遍历所有线性组合。它根据总和记录每个元素的组合。

后半部分简单地获取最大值和return数组。

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

Javascript 查找最大子数组的函数

Javascript function that finds largest subarray

javascript

kadanes-algorithm