求连续最大和子序列

Q:在一个数组中,元素可能有正整数,0,负整数,求其一个连续的子序列,使得该子序列的元素相加之和是所有连续子序列和最大的。
例如:数组[1,2,-5,3,0,-1,2,-4,3],其最大和的子序列为[3,0,-1,2],其最大和为4,实现其代码。

一道算法中常见的面试题,正好我也碰到了,那就来看下js版本如何实现。
其实什么语言实现都一样,关键还是思路,我们理一下思路。首先,相加的和要最大,相加的情况分三种:

  1. 正正相加,正数与正数相加,毫无疑问和一定是越来越大的。
  2. 负负相加,负数与负数相加,那一定是越来越小。
  3. 正负相加,正数与负数相加,这里要注意下,相加之后和可能大于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

以上,就是具体的代码实现。其实这个问题设计到一个概念,动态规划,感兴趣的同学或者有疑问的可以自行看下,因为我也不会(逃

菜鸟学习笔记,如有不对,还希望高手指点。如有造成误解,还希望多多谅解。

著作权归作者所有。
商业转载请联系作者获得授权,非商业转载请注明出处。