Q：在一个数组中，元素可能有正整数，0，负整数，求其一个连续的子序列，使得该子序列的元素相加之和是所有连续子序列和最大的。
例如：数组[1,2,-5,3,0,-1,2,-4,3]，其最大和的子序列为[3,0,-1,2]，其最大和为4，实现其代码。
一道算法中常见的面试题，正好我也碰到了，那就来看下js版本如何实现。
其实什么语言实现都一样，关键还是思路，我们理一下思路。首先，相加的和要最大，相加的情况分三种：
- 正正相加，正数与正数相加，毫无疑问和一定是越来越大的。
- 负负相加，负数与负数相加，那一定是越来越小。
- 正负相加，正数与负数相加，这里要注意下，相加之后和可能大于0，可能等于0，可能小于0，但要实现题目的和最大，即使你是正负相加，也肯定要取你相加之后大于0的负数。
可以得出结论：假设你初始值是0，碰到正数就相加并累计序列，碰到负数相加和为正也相加并累计，碰到负数如果相加和为负就舍弃，重新累计序列。换成代码逻辑就是，遍历数组时，对于每一位数，先取出前一位的信息进行判断前面连续子序列的总和，如果总和大于等于0，则将自己与前面进行拼接，否则只保留自身，以此生成处理信息传递给下一位处理。
下面给出js版本的代码实现:
// 关键之处就是getNewSeqFromPrevSeq方法得判断前面连续子序列的总和，大于0，就拼接并累计值，小于0，舍弃之前子序列，保留自身，重新累计值。
function getNewSeqFromPrevSeq(prevSeq, currentValue){
const newSeq = prevSeq.sum > 0 ? [...prevSeq.seq, currentValue] : [currentValue] // 这里判断上个子序列是否大于(或等于)，取决于你相加等于0要不要拼接子序列
const newSum = prevSeq.sum > 0 ? prevSeq.sum + currentValue : currentValue
return { seq: newSeq, sum: newSum }
}
function getMaxSubSeq(arr){
if (!Array.isArray(arr) || arr.length <= 0 ) return
const result = []
result.push({ seq: [arr[0]], sum: arr[0] }) // 初始化数组第一项为最大和子序列
for (let i = 1; i < arr.length; i++) {
const temp = getNewSeqFromPrevSeq(result[i-1], arr[i])
result.push(temp) // 这里的result是存放所有的子序列集合，后续直接进行最大子序列和最大和的判断
}
// 求最大子序列和最大和
let max = -99999
let seq = []
result.forEach((v, i) => {
(v.sum > max) && (max = v.sum, seq = v.seq)
})
console.log(`输入：${arr}`)
console.log(`输出：连续最大和子序列为${seq}, 最大和为${max}`)
}
var arr = [1,2,-5,3,0,-1,2,-4,3]
getMaxSubSeq(arr) // 输出：连续最大和子序列为3,0-1,2, 最大和为4
以上，就是具体的代码实现。其实这个问题设计到一个概念，动态规划，感兴趣的同学或者有疑问的可以自行看下,因为我也不会（逃
菜鸟学习笔记，如有不对，还希望高手指点。如有造成误解，还希望多多谅解。
著作权归作者所有。
商业转载请联系作者获得授权,非商业转载请注明出处。