JS 求数组中 和最大的连续子串？

Question

input:数组 类似于 [-2, 1, -3, 4, -1, 2, 1, -5, 4]
output： 6: [4, -1, 2, 1]
如何做啊？

Answer 1

//通过每次与前一位的最大连续子串的信息做比较进行拼接function getTempByPrevSeq(PrevTemp, currentValue) {&nbsp; &nbsp; //这里规定，0也可以进行子串拼接&nbsp; &nbsp; if (PrevTemp.sum >= 0) {&nbsp; &nbsp; &nbsp; &nbsp; return {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; num: PrevTemp.num + 1,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum: PrevTemp.sum + currentValue&nbsp; &nbsp; &nbsp; &nbsp; };&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; return {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; num: 1,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum: currentValue&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}function getMaxSumSeqArr(input) {&nbsp; &nbsp; if (input.length === 0) return;&nbsp; &nbsp; var temps = []; // 存储每一位与前面连续之后可得最大值的信息，以便后面的每一位进行迭代更新&nbsp; &nbsp; //第一位向前的最大子串就是它自己本身&nbsp; &nbsp; var temp = {&nbsp; &nbsp; &nbsp; &nbsp; num: 1,&nbsp; &nbsp; &nbsp; &nbsp; sum: input[0]&nbsp; &nbsp; };&nbsp; &nbsp; temps.push(temp);&nbsp; &nbsp; for (var i = 1, len = input.length; i < len; i++) {&nbsp; &nbsp; &nbsp; &nbsp; var ref = input[i];&nbsp; &nbsp; &nbsp; &nbsp; //从前向后迭代&nbsp; &nbsp; &nbsp; &nbsp; var temp = getTempByPrevSeq(temps[i-1], ref);&nbsp; &nbsp; &nbsp; &nbsp; temps.push(temp);&nbsp; &nbsp; }&nbsp; &nbsp; //存储了迭代过程中的信息, 可以在这里看看&nbsp; &nbsp; console.log(temps);&nbsp; &nbsp; var maxValue, //获取最大值&nbsp; &nbsp; &nbsp; &nbsp; indexArr = []; //获取多个结果的index&nbsp; &nbsp; maxValue = temps[0].sum;&nbsp; &nbsp; indexArr.push(0);&nbsp; &nbsp; for (var i = 1, len = temps.length; i < len; i++) {&nbsp; &nbsp; &nbsp; &nbsp; var ref = temps[i];&nbsp; &nbsp; &nbsp; &nbsp; if (ref.sum === maxValue) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; indexArr.push(i);&nbsp; &nbsp; &nbsp; &nbsp; } else if (ref.sum > maxValue) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxValue = ref.sum;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; indexArr.length = 0; //重置数组&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; indexArr.push(i);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; //output&nbsp; &nbsp; console.log("MaxValue: " + maxValue);&nbsp; &nbsp; for (var i = 0, len = indexArr.length; i < len; i++) {&nbsp; &nbsp; &nbsp; &nbsp; var index&nbsp; &nbsp; &nbsp;= indexArr[i],&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ref&nbsp; &nbsp; &nbsp;= temps[index];&nbsp; &nbsp; &nbsp; &nbsp; console.log(input.slice(index-ref.num+1, index+1));&nbsp; &nbsp; }}var input = [-2, 1, -3, 4, -1, 2, 1, -5, 4];getMaxSumSeqArr(input);该算法效率为o(n)。对于每一位数，先取出前一位的信息进行判断前面连续子串的总和，如果总和大于等于0，则将自己与前面进行拼接，否则只保留自身，以此生成处理信息传递给下一位处理。