有长度为n 的数组，其元素都是int型整数（有正有负）。在连续的子数组中找到其和为最大值的数组。
如 [1, -2, 3, 10, -4, 7, 2, -5]的最大子数组为[3, 10, -4, 7, 2]
直接使用循环，时间复杂度O(n^3)，太高了，哈哈。
分治的思想在解题过程中是经常用到的，可以通过递归的计算，将复杂的事情简单化，并且时间复杂度能够降到跟树结构一样，为O(nlgn)
思考下： 选定一个基准，数组中间那位数。那么最大子数组出现的位置会有这么几种情况：
但是这样并不能知道最大子数组的元素，如何修改才可以呢？为了得到位置信息，那么在每次迭代的时候除了子数组的和我们还需要表示位置的值，也就是要返回多个值。
在js中函数不能返回两个基本类型值，但是可以返回数组或者对象
在这我采用了数组，因为我们在计算左右两侧maxSubArray的返回值时，分别需要不同的变量来接收。
因为有正有负，所以子数组的和的最大值肯定为正值（哪怕该子数组只有一个正数）。（思考下：如果数组中全是负数时呢？）
其次可以得出：最大子数组的第一个元素、最后一个元素肯定为正值。
开始遍历数组，记录两个变量 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).
回答前面留下的思考：如果考虑到数组中全是负数的情况呢？
上面是根据 current_sum 是否小于0来决定 current_sum是 是否开始记录新的子数组的和。在数组向后扫描时，针对a[i+1]有两种选择：
那么判断条件是什么呢？是 current_sum +a[i] 与 a[i] 的值的比较。如果a[i]加上前面的和却更小，那就将其作为新数组的第一项，同时更新记录数组位置的值。
前言面试遇到一个问题：JS数组求和函数。我第一想到的就是数组循环。然而我觉得面试官问这个问题一定不是想考这个人人皆知的方法。当时机智的我竟然想到了递归函数不断加和数组的项，然而折腾了好久都没调好方法，事实证明这并不是最优解。最后面试官问我有没有见过reduce()，真木有哇。所以回来查资料，Array.reduce()是ES5新增的新属性，相似的还有Array.reduceRight()。
下文来总结一下数组求和的方法。
最粗暴的方法：循环获取
通过for循环一项项地加和。看代码：
Array.prototype.sum
=
function
(){
var
result
=
0
for(var
i
=
0
i
<
this.length
i++)
{
result
+=
this[i]
}
return
result
}
[1,4,7,2,10].sum()
//
24
使用reduce方法
利用reduce方法，可以写一个数组求和的sum方法。
reduce()方法接收一个函数作为累加器，数组中的每个值(从左到右)开始缩减，最终为一个值。
reduce的语法：
array.reduce(callback[,
initialValue])
callback函数接受4个参数：previousValue(上次调用回调返回的值)、currentValue(当前被处理的元素)、index(索引)以及数组本身(第一次调用
callback的第一个参数)，执行数组中每个值的函数。
initialValue参数可选，表示初始值；initialValue参数若指定，则当作最初使用的previous值，如果缺省，则使用数组的第一个元素作为previous初始值，同时current往后排一位。
Array.prototype.sum
=
function
(){
return
this.reduce(function
(partial,
value){
return
partial
+
value
})
}
[1,4,7,2,10].sum()
//
24
相比第一种方法，使用reduce()方法的效率更高。
这两种方法的效率比较可以直接在函数运行前后分别调用new
Date()获取即时时间，从而通过时间差比较执行时间。这里就不比较了，因为每个人的执行环境差异较大。测试结果是reduce()方法的执行时间更短。
JS数组求和函数，并求出数组中的最大值
实例代码
<!DOCTYPE
html
PUBLIC
"-//W3C//DTD
XHTML
1.0
Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html
xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta
http-equiv="Content-Type"
content="text/html
charset=gb2312"
/>
<title>脚本之家_js数组求和和最大值方法_脚本之家网</title>
<meta
name="keywords"
content="站长,网页特效,网页特效代码,js特效,js脚本,脚本,广告代码,jb51.net,www.jb51.net,脚本之家网"
/>
<meta
name="description"
content="www.jb51.net,脚本之家网，站长必备js特效及广告代码。大量高质量js特效，提供高质量广告代码下载,尽在脚本之家网"
/>
</head>
<body>
<a
href="http://www.jb51.net/">脚本之家网</a>,站长必备的高质量网页特效和广告代码。jb51.net，站长js特效。<hr>
<script
type="text/javascript">
//求和
Array.prototype.sum
=
function
()
{
for
(var
sum
=
i
=
0
i
<
this.length
i++)sum
+=
parseInt(this[i])
return
sum
}
//求最大值
Array.prototype.maxima
=
function
()
{
for
(var
i
=
0,
maxValue
=
Number.MIN_VALUE
i
<
this.length
i++)parseInt(this[i])
>
maxValue
&&
(maxValue
=
this[i])
return
maxValue
}
//应用
var
arr
=
[1,21,3,4,22,45,60,7,32]
alert(arr.join("+")
+
"="
+
arr.sum())
alert(arr.join("|")
+
"中,
最大的数是:"
+
arr.maxima())
</script>
</body>
</html>
以上就是本文的全部内容，希望对大家使用JavaScript有所帮助哦，如果有疑问的话欢迎留言讨论，小编会及时回复大家的。
// 数组求和除了一般的for，while, foreach, map, filter难道就没有更简单的方法了？？// 答案肯定是 NO NO NO！
// 数组的 reduce() 和 reduceRight() 求和方法！
示例[ES6]:
let numList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log(numList.reduce((n,m) => n+m))
// 结果: 55
// 注意: 如果看不懂箭头函数的小伙伴们，请先了解下ES6。实在没空，下边附上ES5语法示例！
示例[ES5]:
var numList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log(numList.reduce(function (n, m) {
return n + m
}))
// 综上所述: reduce() 和 reduceRight()效果一样，唯一不一样的就是一个从左开始算，一个从右开始算！
