首页 > 试题广场 >

连续子数组最大和

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

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

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

输入描述:

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

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

输出描述:

最大和的结果

示例1

输入

输出

说明

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

算法知识视频讲解

小青蛙黄杨

题目要求最大和，可以使用“穷举法”来遍历所有连续的子数组来完成，但它的复杂度是O(n^2)，不符合出题者的要求。既然是求最大和，那它就是在找寻最优解，这个过程并不需要遍历所有连续子数组。通常可以使用动态规划对问题进行“减治”，降低复杂度。

原题显然等价于“对数组中的任意元素，若我们知道以它作为最后一个元素的所有连续子数组的最大和是多少，那么原问题的解就是在这n个最大和中最大的那个。”

再来看如何求解“对数组中的任意元素，若我们知道以它作为最后一个元素的所有连续子数组的最大和是多少”。因为有了2个限制条件“连续”、“它是最后一个”，那么问题又可以再次“减治”，等价于“若我们知道它上一个元素作为最后一个元素的所有连续子数组的最大和是多少，只要它不是负数，那么此问题就是它加上最后一个元素的值，否则直接用最后一个元素的值即可”。

发表于 2019-07-21 10:41:55 回复(2)

Python

给弟弟一个offer

def largestSubSum(nums):
    for i in range(1,len(nums)):
        if nums[i-1] > 0:
            nums[i] = nums[i-1]+nums[i]
    return max(nums)

感觉前面的答案都比较复杂。。。

我的思路比较简单，实时保存大于0已经经过的subset的和，因为只要第i个数nums[i]，前面的任意连续和是大于0，那么nums[i-1]+nums[i]一定大于nums[i]。在遍历了一次nums中所有的数返回其中最大的数就是连续subset最大的和了

比如：

输入：nums = [3, 10, -4, -7, -2, -4, -5, 10, 20]

遍历一遍后，更新为nums = [3, 13, 9, 2, 0, -4, -5, 10, 30]

发表于 2019-07-19 02:37:38 回复(6)

abserver

提供两种看起来不一样，本质上是一样的算法。

算法来自网站geeksforgeeks，Largest Sum Contiguous Subarray。

思路：

1 求最大连续子数组的和

1 设置一个能使连续子数组的和增大的框集，让该框集遍历整个数组 //即，该框集和总是为正数，一旦框集和为负数，框集前移

2 记录该框集最大时的结果

1.2中记录的变量即是所求结果

算法1：

int maxSubArraySum(int[] a)
{
    int biggestSum = 0, frameSetSum = 0;
    for (int i = 0; i <= a.length - 1; i++)
    {
        frameSetSum = frameSetSum + a[i]; //框集扩增
        if(biggestSum < frameSetSum);
    {
            biggestSum = frameSetSum; //记录最大框集
    }
        if (frameSetSum < 0)
        {
            frameSetSum = 0; //发现框集已不能使连续子数组和增大，框集前移
        }
    return biggestSum;
}

算法2：

int maxSubArraySum(int[] a)
{
    int frameSetSum = a[0];
    int biggestSum = a[0];
    for (int i = 1; i < a.length; i++)
    {
        frameSetSum = Math.max(a[i], frameSetSum + a[i]); //第一个变量大则框集前移，第二个变量大则框集扩增
        biggestSum = Math.max(biggestSum, frameSetSum); //记录遍历过程中最大的子数组和
    }
    return biggestSum;
}

可以看到，算法2中的两句max完全可以由算法1中的两个if替代。思路是完全一样的。

编辑于 2019-07-10 13:58:29 回复(2)

acqierement...

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] dp = new int[n];
        dp[0] = input.nextInt();
        int res = dp[0];
        for (int i = 1; i < n; i++) {
            int num = input.nextInt();
            dp[i] = dp[i - 1] > 0 ? dp[i - 1] + num : num;
            res = Math.max(res, dp[i]);
        }
        System.out.println(res);
    }
}

发表于 2020-03-18 13:36:47 回复(0)

Python

ElonB

"""
动态规划，连续子序列的最大和
dp[i]为i为结束点的子序列最大和
"""
if __name__ == '__main__':
    n = int(input())
    a = []
    for _ in range(n):
        a.append(int(input()))
    dp = [a[0]]
    for i in range(1, n):
        dp.append(max(0, dp[-1]) + a[i])
    print(max(dp))

编辑于 2019-09-29 19:32:47 回复(0)

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)

桃园饭桶

比较容易想到的应该是动态规划吧，而且挺容易理解的。设dp[i]表示这个连续子数组以索引i结束时最大和。最后遍历填充完dp后，真实的最大连续子数组和肯定以某个索引结束的，所以找到dp中最大值即可。填充dp时，如果dp[i-1] < 0，那么dp[i]直接等于第i个数nums[i]，否则就是dp[i] = dp[i-1] + nums[i]。这个应该很容易理解。

 int main () {
    int n = 0, temp = 0;
    cin >> n;
    vector<int>  nums, dp(n, 0);
    while (cin >> temp) nums.push_back(temp);
    dp[0] = nums[0];
    for (int i = 1; i < n; i++) {
        if (dp[i-1] < 0) dp[i] = nums[i];
        else dp[i] = dp[i-1] + nums[i];
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    return 0;
}

发表于 2019-12-10 16:00:24 回复(4)

四星

n = int(input())
c = []
for i in range(0,n):
    c.append(int(input()))
    
if max(c)<=0:
    print(max(c))
else:
    i=1
    new = c[0] 
    pre = c[0]
    while(i<n):
        if pre +c[i] >0:
            pre = pre + c[i]
            i = i+1
            if pre > new:
                new = pre
        else:
            pre = 0 
            i = i+1
    print(new)

发表于 2019-10-19 19:14:33 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,x,t=0,Max=-INT_MAX;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        t += x;
        Max = max(Max, t);
        t = max(t, 0);
    }
    cout<<Max<<endl;
    return 0;
}

发表于 2019-10-17 01:03:44 回复(0)

lrf_jor

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int N;
    vector<int> arr;
    while(cin>>N){
        int tmp;
        //保存数组
        for(int i=0;i<N;i++){
            cin>>tmp;
            arr.push_back(tmp);
        }
        int dp[N];//动态规划
        for(int i=0;i<N;i++){
          if(i==0)dp[i]=arr[i];
          else dp[i]=max(arr[i],dp[i-1]+arr[i]);//状态方程
        }
        int max_rst=dp[0];//找最大和的值
        for(int i=0;i<N;i++){
            if(dp[i]>max_rst)max_rst=dp[i];
        }
        cout<<max_rst<<endl;
    }
}

简单的动态规划

发表于 2019-09-07 11:22:33 回复(0)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>num(n),dp(n,0);
    for(int i=0;i<n;i++)
        cin>>num[i];
    dp[0]=num[0];
    int res=dp[0];
    for(int i=1;i<n;i++)
    {
        if(dp[i-1]+num[i]<0)
            dp[i]=0;
        else
        {
            dp[i]=dp[i-1]+num[i];
            res=max(res,dp[i]);
        }
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-08-22 22:09:56 回复(2)

番茄加两个蛋蛋

function out(arr){ if(arr[0] == 1){ return arr[1]
    } var max = 0  var tem = 0  for(let i=1; i<arr.length;i++) {   tem += arr[i]
        max = Math.max(tem,max) if(tem <= 0) {
            tem =0  }
    } return max
}

发表于 2019-08-19 16:25:50 回复(0)

呦呵呵

动态规划

importjava.util.*;

publicclassMain{

publicstaticvoidmain(String args[]){

Scanner cin = newScanner(System.in);

//输入数组长度

intn = cin.nextInt();

int[] arr = newint[n];

//输入n行数据

for(inti=0;i<n;i++){

arr[i] = cin.nextInt();

}

System.out.println(maxValue(arr,n));

}

//求最大和

publicstaticintmaxValue(int[] arr,intn){

//创建数组dp，大小为arr数组大小

int[] dp = newint[n];

//dp[i]表示从arr[0]到arr[i]的最大和

dp[0] = arr[0];

intmaxValue = dp[0];

for(inti=1;i<n;i++){

//dp[i]的值可能为dp[i-1]+arr[i]，也可能为arr[i]，取最大值

dp[i] = Math.max(dp[i-1]+arr[i], arr[i]);

if(dp[i]> maxValue){

maxValue = dp[i];

}

returnmaxValue;

}

发表于 2019-08-18 15:52:47 回复(0)

改个名字没人认识我

import java.util.*;
public class Main {
     public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int x=sc.nextInt();
        int sum=sc.nextInt();
        int max=sum;
        for (int i = 0; i < x-1; i++) {
            sum+=sc.nextInt();
            if(max<sum)
                max=sum;
            if(sum<0)
                sum=0;
        }
        System.out.println(max);
     }
}

发表于 2019-07-25 16:01:47 回复(0)

big_dreamer

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }

        int[] sums = new int[N];
        sums[0] = nums[0];
        int max = sums[0];
        for (int i = 1; i < N; i++) {
            sums[i] = Math.max(nums[i], sums[i - 1] + nums[i]);
            max = Math.max(max, sums[i]);
        }

        System.out.println(max);
    }
}

编辑于 2019-07-23 18:28:31 回复(0)

C/C++

喜欢ctrl的cxk

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int sum = -1, temp = 0;
    for(int i = 0; i < N; i++)
    {
        int _;
        cin >> _;
        temp += _;
        if(temp < 0)
        {
            temp = 0;
        }
        else
        {
            sum = max(sum,temp);
        }
    }
    cout << sum << endl;
    return 0;
}

发表于 2019-07-12 11:36:12 回复(0)

C/C++

素描青春_/~

#include<stdio.h>
#include<limits.h>
#include<vector>
using std::vector;
int main(){
    int N, temp, max = INT_MIN;
    scanf("%d", &N);
    vector<vector<int> > vv(N, vector<int>(N));
    //二维数组赋第一行值，找第一行最大值，子数组唯一个元素
    for (int i = 0; i < N; ++i){
        scanf("%d", &temp);
        vv[0][i] = temp;
        max = max > temp ? max : temp;
    }
    //循环到结束，子数组为2-N个元素，并找最大值
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j++){
            vv[i][j] = vv[0][j] + vv[i - 1][j - 1];
            max = max > vv[i][j] ? max : vv[i][j];
        }
    }
    printf("%d", max);
    return 0;
}

编辑于 2019-06-30 21:03:12 回复(0)

一个小太阳

public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int arrLen = sc.nextInt();
        int []arr = new int[arrLen];
        for(int i=0;i<arrLen;i++) {
            arr[i] = sc.nextInt();
        }

        int max = arr[0];
        int sum = 0;
        //遍历每一项
        for (int i=0;i<arr.length;i++) {
            if(sum>=0) {
                sum+=arr[i];
            }else {
                sum = arr[i];
            }
            if(sum>max) {
                max = sum;
            }

        }
        System.out.println(max);
        sc.close();
    }

发表于 2019-06-21 14:45:49 回复(0)

Java

asuren

思路：求出每个位置的累加和，标记最大累加和、最小累加和的位置，分别记为i和j

如果i>j，且sums[j]为负数，说明最大和的连续子数组在i和j之间，返回sums[i]-sums[j]

如果i<=j，说明最大和的连续子数组在0和j之间，返回sums[i]

arr[]: 1 -2 3 10 -4 7 2 -5

sums[]: 1 -1 2 12 8 15 17 12

min max

结果 = 17 - （-1） = 18

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] arr = new int[N];
        
        for(int i=0;i<N;i++){
            arr[i] = scanner.nextInt();
        }
        int[] sums = new int[N];
        sums[0]=arr[0];
        
        int max = 0;
        int min = 0;
        
        for(int i=1;i<N;i++){
            sums[i] = sums[i-1]+arr[i];
            max = sums[max]>sums[i]?max:i;
            min = sums[min]<sums[i]?min:i;
        }
        if(max>min){
            int ret = sums[max]>sums[max]-sums[min]?sums[max]:sums[max]-sums[min];
            System.out.println(ret);
        }else{
            System.out.println(sums[max]);
        }
    }
}

发表于 2019-07-06 19:57:26 回复(0)

拿offer拿到手软666

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int curmax = 0, imax = -999;
    int tmp;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        curmax += tmp;
        imax = max(imax, curmax);
        curmax = max(curmax, 0);
    }
    cout << imax << endl;
    return 0;
}

编辑于 2019-06-14 21:36:03 回复(11)