Find max sub array

  • Key point
    1. Sub array : continuous index in the array with at least one element
  • Approaches
    1. Brute-force
// My brute force solution
var a = [7, -1, -2, -4, 5, 3, -10, -1, 20]; 
console.log(findMax(a));

function findMax(a){
    var max = {
        val : undefined,
        index : undefined,
    };

    for(var i=0; i<a.length; i++){
        if(i==0){
            max.val = a[0];
            max.index = i;
        }

        for(var j=i+1; j<a.length; j++){
            if(max.val<a[j]){
                max.val = a[j];
                max.index = j;
            }else{
                var temp = _sum(a,i,j)
                if(max.val<temp){
                    max.val = temp;
                    max.index = [i,j];
                }
            }
        }
    }

    return max;
}


function _sum(a,i,j){
    var sum = 0;
    if(j>=i){
        for(var k=i; k<=j; k++){
            sum += a[k];
        }
    }
    return sum;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。