连续子数组最大和

[编程题]连续子数组最大和

热度指数：28491 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入一个整形数组（可能有正数和负数），求数组中连续子数组（最少有一个元素）的最大和。要求时间复杂度为O(n)。

输入描述:

【重要】第一行为数组的长度N（N>=1）

接下来N行，每行一个数，代表数组的N个元素

输出描述:

最大和的结果

示例1

输入

输出

说明

最大子数组为 3, 10, -4, 7, 2

算法知识视频讲解

JavaScript

萌萌萌哒

JavaScript(Node) 😎题目:英语流利说-连续子数组最大和

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
let n
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    n = +inArr[0]
    if(inArr.length === n+1){
        let arr = []
        for (let i = 0; i < n; i++) {
             arr[i] = +inArr[i+1]
        }
        console.log(maxsum(arr))
    }
})
function maxsum(arr) {
    if(arr.length === 1){
        return arr[0]
    }
    let max = 0, temp = 0
    for (let i = 0; i < arr.length; i++) {
        temp += arr[i]
        max = Math.max(temp,max)
        if(temp<0){
            temp = 0
        }
    }
    return max
}

发表于 2020-02-26 12:44:44 回复(0)

JavaScript

onlyTry

思路：从第一个数字开始遍历，判断当前数字与累加和的大小，如果当前数字大（比如题例中1+(-2)+3 = 2 < 3），就让连续子数组之和从当前数字重新开始计算，在此遍历过程中得到的最大值即所求的连续子数组最大和。

注意：由于测试用例的输入可能只有一个数字，所以直接读取第一个数字来初始化，而不是将累加和初始化为0，因为第一个数有可能是负数。

var N = parseInt(readline());
var currNum = parseInt(readline()),
    tempSum = currNum,
    subArrSum = currNum;

for(var i=1; i<N; i++){
    currNum = parseInt(readline()),
    tempSum += currNum;
    tempSum = tempSum > currNum? tempSum: currNum;
    subArrSum = Math.max(subArrSum,tempSum);
}
print(subArrSum);

发表于 2019-08-19 10:15:31 回复(0)