Find max sub array

作者: 超薄智能 | 来源:发表于2018-08-05 22:47 被阅读6次

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