首页 > 试题广场 >

最大序列和

[编程题]最大序列和

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

给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。对于S的所有非空连续子序列T，求最大的序列和。变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。

输入描述:

第一行为一个正整数N，第二行为N个整数，表示序列中的数。

输出描述:

输入可能包括多组数据，对于每一组输入数据，
仅输出一个数，表示最大序列和。

示例1

输入

5
1 5 -3 2 4

6
1 -2 3 4 -10 6

4
-3 -1 -2 -5

输出

9
7
-1

算法知识视频讲解

GrantLeung

#include<iostream>
#include<vector>
using namespace std;
void cal(vector<int> p,int n)
{
    long int p_max = p[0];//用于接受循环时的数组最大值，初始为第一个数
    //int x;
    long int sum = p[0];//用于接收循环时的数组累加值，初始为第一个数
    for(int i=1;i<n;i++)
    {
        //x = p[i];
        sum = sum+p[i];//累加
        if(p[i]>sum)
            sum = p[i];//如果当前的这个数比累加值大，那么从此数开始重新判断序列
if(sum > p_max)
        {
            p_max = sum;//如果累加值大于此前得出的最大值，那么最大值必然是累加值
        }

    }
    cout<<p_max;
}
int main()
{
    int N;
    int t;
    cin>>N;
    vector<int> a;//设定动态数组
    for(int i=0;i<N;i++)
    {
        cin>>t;
        a.push_back(t);
    }
     //int n=sizeof(a)/sizeof(int);
     cal(a,N);//执行函数
     //cout<<n;
     return 0;
}

发表于 2018-03-29 12:38:39 回复(0)

C/C++

熊熊儿

//这道题用分治法也能做的O(nlogn)的复杂度
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 1000005
int n, arr[N];
///法一: 分治法 AC 234ms
int solve_01 ( int lo, int hi )
{
    int mi = ( lo + hi ) >> 1;
    if ( hi - lo <= 1 )
        return arr[lo];
    int lc, rc, l = -INF, r = -INF;
    lc = solve_01 ( lo, mi ); //[lo, mi)
    rc = solve_01 ( mi, hi ); //[mi, hi)
    int sum = 0;
//!之前将i>=lo写成了i>=0,i<hi写成了i<n,所以变成了一个O n*n的算法而超时
    for ( int i = mi - 1; i >= lo; i -- )
    {
        sum += arr[i];
        l = l < sum ? sum : l;
    }
    sum = 0;
    for ( int i = mi; i < hi; i ++ )
    {
        sum += arr[i];
        r = r < sum ? sum : r;
    }
    int max = l + r;    //!max是跨越中间的序列最大值
    max = max < lc ? lc : max;
    max = max < rc ? rc : max;
    return max;
}
int main ( )
{
    while ( cin >> n )
    {
        for ( int i = 0; i < n; i ++ )
            cin >> arr[i];
        cout << solve_01 ( 0, n ) << endl;
    }
    return 0;
}

编辑于 2018-05-06 12:27:27 回复(0)

C++

erenn

个人感觉非常好，运行时间一般，但内存占用非常低，代码量也少

long long的最小值好像没找到类似INT_MIN之内的常量，就直接用16进制表示了

#include <iostream>

using namespace std;

int main(){
    
    int n;
    while( cin >> n){
        long long sum = 0;
        long long subMax = 0x8000000000000000;
        while(n--){
            int x;
            cin >> x;
            sum += x;
            if(sum > subMax) subMax = sum;
            if(sum < 0) sum = 0;
        }
        cout << subMax <<endl;
    }
    
}

发表于 2022-01-09 13:02:00 回复(0)

C++

之一不之

动态规划

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000;
long long dp[maxn];
long long a[maxn];

long long Maxi(int n){
    long long maximum=0;
    for(int i=0;i<n;i++){
        if(i==0){
            dp[i]=a[i];
            maximum=dp[i];
        }else{
            dp[i]=max(a[i],dp[i-1]+a[i]);
        }
        maximum=max(maximum,dp[i]);
    }
    return maximum;
}

int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        memset(dp,0, sizeof(dp));
        long long ans=Maxi(n);
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2021-08-30 21:51:57 回复(0)

sunX&Y

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int maxn = 1e6;

ll a[maxn+5], dp[maxn+5];
int n;

ll DP()
{
    ll MAX = -INF;
    dp[0] = 0;
    for(int i = 1;i <= n; i++)
    {
        dp[i] = max(a[i], dp[i-1]+a[i]);
        if(dp[i] > MAX) MAX = dp[i];
    }
    return MAX;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n)
    {
        for(int i = 1;i <= n; i++) cin >> a[i];
        cout << DP() << '\n';
    }
    return 0;
}

发表于 2021-04-03 15:12:34 回复(0)

C/C++

YhX.

#include<stdio.h>//子序列累加问题   借助悟空大佬的思路
int max(int a,int b)
{
    return a>b?a:b;
}
int main(){
    int N,i;
    while(scanf("%d",&N)!=EOF){//输入N个数
        long int sum=0,Max=-999999999,x;//长整型
        for(i=0;i<N;i++){//每输入一个数,
            scanf("%ld",&x);//比较也就是最大值与 新加一个数的和 与 新加的这一个数 三个值相比较
            sum=max(sum+x,x);//先比较输入的数与之前序列和+此数谁大,取大值做累加和
            Max=max(Max,sum);//比较之前的Max与新的序列和谁大
        }
        printf("%ld\n",Max);
    }
}

发表于 2020-03-24 17:38:18 回复(0)

C/C++

月哟

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        vector<int> arr(n),dp(n);
        for(auto& x:arr)
            scanf("%d", &x);
        dp[0] = arr[0];
        for (int i = 1; i < n;i++)
            dp[i] = max(dp[i - 1] + arr[i], arr[i]);
        printf("%d\n", *max_element(dp.begin(), dp.end()));
    }
    return 0;
}

C++11真香

编辑于 2020-03-09 02:17:59 回复(0)

小刀初试

首先将最大的数作为ans；

然后遍历数组，逐个累加到s中，如果s+i>0则将i加入到s中，并将ans=max(ans,s)；

如果s+i小于0，将s=0.

#include <bits/stdc++.h>
using namespace std;
int main(){
	for(int N,s,ans,i;cin>>N;){
		vector<int> v(N,0);
		for(i=0;i<N;cin>>v[i++]);
		for(s=i=0,ans=v[0];i<N;++i){
			ans=(ans>v[i]?ans:v[i]);
			if (s+v[i]>0){
				s+=v[i];
				ans=(ans>s?ans:s);
			}
			else s=0;
		}
		cout<<ans<<endl;
	}
	return 0;
}

发表于 2016-08-31 20:38:24 回复(0)

元气の悟空

#include<stdio.h>
#include<algorithm>
//#include<windows.h>
using namespace std;
int main(){
	int N,i;
	//freopen("input.txt","r",stdin);
	while(scanf("%d",&N)!=EOF){
		long sum=0,Max=-999999999,x;
		for(i=0;i<N;i++){
			scanf("%ld",&x);
			sum=max(sum+x,x);
			Max=max(Max,sum);
		}
		printf("%ld\n",Max);
	}
}

发表于 2017-08-05 11:05:56 回复(14)

ABCDEF

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
int dp[1000010];
int a[1000010];
long long maxx;
int main()
{
    int n ;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        dp[0] = a[0];
        maxx = 0;
        for(int i=1;i<n;i++){
            dp[i] = max(dp[i-1]+a[i],a[i]);
            if(maxx<dp[i]){
                maxx = dp[i];
            }
        }
        cout<<maxx<<endl;
    }
   return 0;
}

简单动态规划。dp[i]表示以a[i]结尾的最大序列和。

编辑于 2017-03-13 21:22:45 回复(3)

C/C++

练习时长两年半的Java练习生

#include<stdio.h>
int main (){//C语言亦可短
    int N,i,t;long max,prev;
    for(;~scanf("%d %d",&N,&t);)
        for(prev=max=t,i = N>1?2:printf("%ld\n",max),1; i <= N && ~scanf("%d",&t) && (prev = prev>0?t+prev:t)>=t && (max=max<prev?prev:max)>=prev ;i==N?printf("%ld\n",max):0,i++);
}

编辑于 2018-03-18 13:02:12 回复(2)

C/C++

牛客144327895号

最大子序列和

算法思想：首先，需要定义ans，sum2个参数。ans记录之前求得最大的子序列之和，初值为-2^63，sum记录当前序列的累加和，初值为0。每当sum累加之和大于ans时，将ans赋值给sum。当sum小于0时，即可证明sum加上下一个值时必定会小于下一个值,所以将sum置0，下一个值开始重新累加，从而保证获得最大子序列和。

/*
最大子序列和 = max（前最大子序列和， 子序列累加和）
子序列累加和 = max（0， 前子序列累加和 + 当前数值）
*/
#include<bits/stdc++.h>
using namespace std;
int num[1000000];
int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        for(int i=0; i<n; i++)
            scanf("%d", &num[i]);
        long long ans = pow(-2, 63);
        long long sum = 0;
        for(int i=0; i<n; i++){
            sum += num[i];
            if(sum > ans)  // 核心代码1
                ans = sum;
            if(sum < 0)    // 核心代码2
                sum = 0;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

发表于 2020-02-29 21:00:04 回复(0)

Python

TimeMac

是不是快炸了？

try:
    while True:
        num = int(input())
        digits = list(map(int,input().split()))
        temp = 0
        result = float('-inf')
        for i in range(num):
            temp = max(temp+digits[i],digits[i])
            result = max(temp,result)
        print(result)
except Exception:
    pass

图片说明

编辑于 2018-10-09 21:37:14 回复(0)

C/C++

成程晨

#include<stdio.h>
#include<math.h>
int main()
{
int N,a[1000000],i,j,k;
long long int s=-pow(2,63),sum;
while(scanf("%d",&N)!=EOF)
{
sum=0;
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
if(sum>s) s=sum;
if(sum<0) sum=0;
}
printf("%d\n",s);
}
return 0;
}

发表于 2018-02-26 17:41:17 回复(0)

Python

华科平凡

python2.7 solution。使用python3无法通过。

while True:
    try:
        a, arr = input(), list(map(int, input().split()))
        cur, res = arr[0], arr[0]
        for i in arr[1:]:
            if cur < 0:
                cur = 0
            cur += i
            res = max(res, cur)
        print(res)
    except:
        break

编辑于 2017-10-17 09:39:10 回复(0)

爱吃姜烩葱

while True:
    try:
        n=int(input())
        s=list(map(int,input().split()))
        dp=[0]*(n+1)
        dp[1]=s[0]
        for i in range(2,n+1):
            dp[i]=max(s[i-1],dp[i-1]+s[i-1])
        print(max(dp[1:]))
    except:
        break

经典dp，dp[i]代表以第i个数结尾的最大子序列和，其为前一个数所求出的最大子序列和加上第i个数的和与第i个数之间较大的那个

编辑于 2024-03-28 19:30:00 回复(0)

C/C++

猫猫猫1

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

const int Max=1000000;
int a[Max];
int dp[Max];

void Fun(int n){
    int answer=a[0];
    for(int i=0;i<n;i++){
        if(i==0){
            dp[i]=a[i];
        }
        else{
            dp[i]=max(a[i],dp[i-1]+a[i]);
        }
        answer=max(answer,dp[i]);
    }
    cout<<answer<<endl;
    return ;
}

int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        Fun(n);
    }
    return 0;
}

发表于 2022-10-16 11:26:00 回复(0)

C/C++

胡桃夹子🎈

#include<iostream>
#include<algorithm>
using namespace std;
long long max_subsquence(long long*& arr, int& n)
{
	long long dp = arr[0];//表示以arr[i]结尾的最长子序列和
	long long ans = dp;//base case边界条件
	for (int i = 1; i < n; i++)
	{
		dp = max(arr[i], dp + arr[i]);//状态转移方程
		ans = max(ans, dp);
	}
	return ans;
}

int main()
{
	int n;
	while (cin>>n)
	{
		long long* arr = new long long[n];
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		cout << max_subsquence(arr, n) << endl;
		delete[] arr;
	}
	return 0;
}

动态规划

编辑于 2020-07-09 10:52:23 回复(0)

ZJ_Lavender

动态规划——

如果前边所有数字的和是一个非负数，那么加在后边是有利于取得最大值。否则加在后边是不利于取得最大值，应当舍去，

整个过程中应当有一个max空间用来保存最大值。

发表于 2016-04-14 16:54:33 回复(0)

zbt_123456

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
   long long n;
   while(cin>>n){
    vector<long long> s(n);
    for(int i =0;i<n;i++){
        cin>>s[i];
    }
    vector<long long> t(n);
    t[0] = s[0];
    for(int i=1;i<n;i++){
        t[i] = max(s[i],t[i-1]+s[i]);
    }
    long long maxsum = *max_element(t.begin(),t.end());
    cout<<maxsum<<endl;
   }
}

编辑于 2024-03-28 21:30:35 回复(0)