找出最大子数组(js实现)

有长度为n 的数组，其元素都是int型整数（有正有负）。在连续的子数组中找到其和为最大值的数组。

如 [1, -2, 3, 10, -4, 7, 2, -5]的最大子数组为[3, 10, -4, 7, 2]

直接使用循环，时间复杂度O(n^3)，太高了，哈哈。

function maxSubArray(arr) {    const len = arr.length;    if (len<=1) {        return arr
    }    let sum = arr[0];    let x_pos=0;    let y_pos=0;    for(let i=0;isum) {
                sum=tmp;
                x_pos=i;
                y_pos=j;
            }
        }
    }    // console.log("sum is",sum)
    return arr.slice(x_pos,y_pos+1)
}

分治的思想在解题过程中是经常用到的，可以通过递归的计算，将复杂的事情简单化，并且时间复杂度能够降到跟树结构一样，为O(nlgn)

思考下： 选定一个基准，数组中间那位数。那么最大子数组出现的位置会有这么几种情况：

• 在基准的左侧；

• 在基准的右侧；

• 横跨基准值，包含其左侧的最大前缀子数组与右侧的最大后缀子数组。

function maxSubArray(arr,left,right) {    if (left>right) {        return 
    }    if (left==right) {        return arr[left]
    }    let pivot=Math.floor((right+left)/2);    let left_max=maxSubArray(arr,left,pivot-1);    let right_max=maxSubArray(arr,pivot+1,right);    let left_tmp=0;    let left_sum=0;    let left_pos=pivot;    for(let i=pivot-1;i>=left;i--){
        left_tmp+=arr[i]        if (left_tmp>left_sum) {
            left_sum=left_tmp
            left_pos=i
        }
    }    let right_tmp=0;    let right_sum=0;    let right_pos=pivot;    for(let i=pivot+1;i<=right;i++){
        right_tmp+=arr[i]        if (right_tmp>right_sum) {
            right_sum=right_tmp
            right_pos=i
        }
    }    let mid_arr = arr.slice(left_pos,right_pos+1)    let mid_max = left_sum+right_sum+arr[pivot]    return Math.max((left_max||0),mid_max,(right_max||0))
}

但是这样并不能知道最大子数组的元素，如何修改才可以呢？为了得到位置信息，那么在每次迭代的时候除了子数组的和我们还需要表示位置的值，也就是要返回多个值。

在js中函数不能返回两个基本类型值，但是可以返回数组或者对象

let [aa,bb]=(function(){return [1,2]})()let {cc,dd}=(function(){return {cc:11,dd:12}})()

在这我采用了数组，因为我们在计算左右两侧maxSubArray的返回值时，分别需要不同的变量来接收。

function maxSubArray(arr,left,right) {    if (left>right) {        //！！！注意此处应该返回函数期待的类型，否则不会迭代下去
        return []
    }    if (left==right) {        //同样修改返回类型
        return [arr[left],left,left]
    }    let pivot=Math.floor((right+left)/2);    let [left_max,pos_left_i,pos_left_j]=maxSubArray(arr,left,pivot-1)||[0,0,0];    let [right_max,pos_right_i,pos_right_j]=maxSubArray(arr,pivot+1,right)||[0,0,0];    let left_tmp=0;    let left_sum=0;    let left_pos=pivot;    for(let i=pivot-1;i>=left;i--){
        left_tmp+=arr[i]        if (left_tmp>left_sum) {
            left_sum=left_tmp
            left_pos=i
        }
    }    let right_tmp=0;    let right_sum=0;    let right_pos=pivot;    for(let i=pivot+1;i<=right;i++){
        right_tmp+=arr[i]        if (right_tmp>right_sum) {
            right_sum=right_tmp
            right_pos=i
        }
    }    let mid_arr = arr.slice(left_pos,right_pos+1)    let mid_max = left_sum+right_sum+arr[pivot]    
    //修改为返回数组信息
    let max_value = Math.max((left_max||0),mid_max,(right_max||0));    if (max_value==left_max) {        return [max_value,pos_left_i,pos_left_j]
    }    if (max_value==right_max) {        return [max_value,pos_right_i,pos_right_j]
    }    return [max_value,left_pos,right_pos]
}

因为有正有负，所以子数组的和的最大值肯定为正值（哪怕该子数组只有一个正数）。（思考下：如果数组中全是负数时呢？）

其次可以得出：最大子数组的第一个元素、最后一个元素肯定为正值。

开始遍历数组，记录两个变量current_sum+=arr[i],max_sum=0，一旦current_sum<0是不是current_sum中记录的连续元素就绝对不可能成为最大子数组？所以此时重置current_sum=0开始从下一个元素记录其连续片段的和。继续与max_sum比较即可。

在循环过程中只要current_sum>max_sum，就设置max_sum =current_sum

这样只需要一个遍历，即可完成对最大子数组和的计算。时间复杂度O(n).

function maxSubArray(arr) {    const len=arr.length;    if (len<=1) {        return arr
    }    //left_pos,right_pos 记录最大子数组的位置信息
    let left_pos=0;    let right_pos=0;    let maxSum=0;    let curSum=0;    for(let i=0;imaxSum) {
            maxSum=curSum
            right_pos=i
        }        if (curSum<0) {
            curSum=0
            left_pos=i+1
        }
    }    let maxArr=arr.slice(left_pos,right_pos+1)    console.log("sub arr is ",maxArr)    return maxSum
}

回答前面留下的思考：如果考虑到数组中全是负数的情况呢？

上面是根据current_sum是否小于0来决定current_sum是是否开始记录新的子数组的和。在数组向后扫描时，针对a[i+1]有两种选择：

• 加入current_sum

• 作为新子数组中的第一项。

那么判断条件是什么呢？是current_sum +a[i]与a[i]的值的比较。如果a[i]加上前面的和却更小，那就将其作为新数组的第一项，同时更新记录数组位置的值。

for(let i=0;i


作者：RichardBillion
链接：https://www.jianshu.com/p/7053d71ca5b6