首页 > 试题广场 > 连续子数组最大和
[编程题]连续子数组最大和

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


输入描述:
【重要】第一行为数组的长度N(N>=1)

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


输出描述:
最大和的结果
示例1

输入

8
1
-2
3
10
-4
7
2
-5

输出

18

说明

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

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

再来看如何求解“对数组中的任意元素,若我们知道以它作为最后一个元素的所有连续子数组的最大和是多少”。因为有了2个限制条件“连续”、“它是最后一个”,那么问题又可以再次“减治”,等价于“若我们知道它上一个元素作为最后一个元素的所有连续子数组的最大和是多少,只要它不是负数,那么此问题就是它加上最后一个元素的值,否则直接用最后一个元素的值即可”。
发表于 2019-07-21 10:41:55 回复(0)
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 回复(4)
import java.util.*;
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 max = nums[0],sum = 0;
        for(int i = 0;i < nums.length;i++){
            sum += nums[i];
            //更新
            if(sum > max)
                max = sum;
            //sum并不是记录最大连续和,只记录大于零的和,只要连续和小于0
            //则重新开始计算和,因为nums[i]加上一个负数肯定比它本身小
            if(sum < 0){
                sum = 0;
            }
        }
        System.out.println(max);
    }
}

发表于 2019-07-29 17:06:12 回复(0)
提供两种看起来不一样,本质上是一样的算法。
算法来自网站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)
"""
动态规划,连续子序列的最大和
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)
#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)
#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)
#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)
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)
#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)
#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)
思路:求出每个位置的累加和,标记最大累加和、最小累加和的位置,分别记为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)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin>>N;
    
    vector<int> arry;
    for (int i=0; i<N; i++)
    {
        int m;
        cin>>m;
        arry.push_back(m);
    }
    
    vector<int> dp;
    int submax=arry[0];
    dp.push_back(submax);
    for (int i=1; i<N; i++)
    {
        dp.push_back(max(dp[i-1]+arry[i], arry[i]));
    }
    
    int MAX=dp[0];
    for (int i=1; i<N; i++)
    {
        MAX = max(MAX, dp[i]);
    }
    
    cout<<MAX<<endl;
    return 0;
}

发表于 2019-10-13 16:10:02 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=Integer.parseInt(sc.nextLine());
            int[] array=new int[n];
            for(int i=0;i<n;i++){
                array[i]=Integer.parseInt(sc.nextLine());
            }
            System.out.println(maxNum(array));
        }
    }
    public static int maxNum(int[] array){
        if(array.length==0||array==null){
            return 0;
        }
        int max=array[0];
        int sum=0;
        for(int a:array){
            if(a+sum>a){
                sum+=a;
            }else{
                sum=a;
            }
            if(sum>max){
                max=sum;
            }
        }
        return max;
    }
}

发表于 2019-10-02 08:42:50 回复(0)
/**
 * 最大连续子序列和
 */
import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        
        //int nums[] = {-8, 1, -2, 3, 10, -4, 7, 2, -5};
        
        
        Scanner sc = new Scanner(System.in);
        int  n = Integer.parseInt(sc.nextLine());
        int nums[] = new int[n];
       for (int j = 0; j < n; j++) {
            nums[j] = Integer.parseInt(sc.nextLine());
        }

        //18

        /*
        可以定义一个dp二维矩阵,规模为M*N,
        其中M,N均等于序列num的长度n,
        dp[i][j]代表从序号i到序号j的连续子序列的和。初始值为0。

        整个程序可以分成两步:
        step1:填充dp矩阵,并用整数max存最大值以及ibegin,iend存最大和序列的开始终止序号;
        step2:输出,max为最大和,ibegin和iend为和为最大值的子序列的开始/结束下标。*/
        int dp[][] = new int[nums.length][nums.length];//0


        int maxNum = 0;
        int ibegin = 0;
        int iend = 0;

        /*(1)填充dp矩阵
                初始值用memset设为0
        当i==j 时,dp[i][j]==num[i]
        其余情况:dp[i][j]=dp[i][j-1]+num[j]
*/

        for (int i = 0; i < dp.length; i++) {
            for (int j = i; j < dp.length; j++) {
                if (i == j) {
                    dp[i][j] = nums[i];
                    if (dp[i][j] > maxNum)
                    {
                        maxNum = dp[i][j];
                        ibegin = i;
                        iend = j;
                    }
                } else {
                    dp[i][j] = dp[i][j - 1] + nums[j];
                    if (dp[i][j] > maxNum)
                    {
                        maxNum = dp[i][j];
                        ibegin = i;
                        iend = j;
                    }
                }
            }
        }

        System.out.println(maxNum);

       // for (int i = ibegin; i <= iend; i++) {
         //   System.out.print(nums[i]+" \t");
      //  }




    }
}

发表于 2019-09-16 15:47:53 回复(0)