JavaScript趣题：求解最大子数组之和

1.[1] sum=>1

2.[1,-1] sum=>0

3.[1,-1,2] sum=>2

4.[-1] sum=>-1

5.[-1,2] sum=>1

6.[2] sum=>2

大家可以看到，这些子数组中，各元素之和最大是2。

那么给定任意一个整数数组，怎样求它的最大子数组之和呢？

如果仔细观察我上面列出子数组的顺序，大家可以看出这是从第一位开始穷举。

嗯，我的方法正是穷举，其执行的过程正是如上所示。

穷举法在这个问题实现的效率其实并不低，可以胜任一般的需求。

我从第一个元素开始，需要遍历N个元素。

第二个元素开始，需要遍历N-1个元素。

......

最后一个元素开始就只有它自己，1个元素。

也就是说，穷举法的实际复杂度是N²/2，这样的效率还是不错的。

function maxContiguousSum (arr) {  
    var max = 0;  
    for(var i=0;i<arr.length;i++){  
        var temp = 0;  
        for(var j=i;j<arr.length;j++){  
            temp += arr[j];  
            if(temp > max){  
                max = temp;  
            }  
        }  
    }  
    return max;  
}

以上就是 JavaScript趣题：求解最大子数组之和的内容，更多相关内容请关注PHP中文网（www.gxlcms.com）！