我要招人

去企业版

首页 > 试题广场 >

最大子序列和

[编程题]最大子序列和

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

给一个长度为N的序列a1,a2,...,an,求最大连续和。也即，寻找1<=i<=j<=N,使得ai+...+aj尽量大。

输入描述:

一行, 整数序列, 逗号分隔

输出描述:

一行, 整数, 表示最大子序列和

示例1

输入

1, 2, -5, 3, 4

输出

算法知识视频讲解

凪咲

使用滑动窗口求解，如果保存最大连续和，如果当前子序列和为负数，则该子序列对后续获得更大的和起副作用，抛弃该部分，重新开始求和。

最大的坑在于明明说用逗号分隔，最后一个用例来了一个先空格再逗号的分隔，这也太阴了。

#include <iostream>
#include <limits.h>

using namespace std;

int main(){
    int cur = 0, ans = INT_MIN, cursum = 0;
    char c='0';
    do{
        while(c == ' '){
            c = getchar();
        }
        cin >> cur;
        cursum += cur;
        ans = max(ans, cursum);
        if(cursum < 0){
            cursum = 0;
        }
        c = getchar();
    }while(c != '\n');
    cout << ans << endl;
    return 0;
}

发表于 2021-09-07 10:32:48 回复(0)

pein531

动规求解，记dp[i]为arr[0:i]的最大连续和，则有状态转移方程

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

表示如果前面的和对arr[i]做的是负贡献，那就从arr[i]开始重新计算连续和，否则继续累加arr[i]。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().trim().split(",");
        int[] arr = new int[strArr.length];
        for(int i = 0; i < arr.length; i++) arr[i] = Integer.parseInt(strArr[i].trim());
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        int max = dp[0];
        for(int i = 1; i < arr.length; i++){
            dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

编辑于 2021-04-12 11:31:30 回复(0)

AlphaScottBing

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arrS = br.readLine().trim().split(",");
        int[] arr = new int[arrS.length];

        int max = Integer.parseInt(arrS[0].trim());
        for (int j = 0; j < arrS.length; j++) {
            arr[j] = Integer.parseInt(arrS[j].trim());
            if (arr[j] > max) {
                max = arr[j];
            }
        }

        int total = 0;
        for (int j : arr) {
            total += j;
            if (total < 0) {
                total = 0;
            } else if (total > max) {
                max = total;
            }
        }
        System.out.println(max);
    }

}

发表于 2024-02-21 23:15:29 回复(1)

C/C++

牛客369884756号

#include <iostream>

#include <sstream>

using namespace std;

int a[10000];

int count = 0;

int hebing(int low, int mid, int high){

int left = a[mid];

int sum1 = a[mid];

for (int i = mid - 1; i >= low; i--){

left = left + a[i];

if(left > sum1) sum1 = left;

}

int right = a[mid + 1];

int sum2 = a[mid + 1];

for (int i = mid + 2; i <= high; i++){

right = right + a[i];

if(right > sum2) sum2 = right;

}

return sum1 + sum2;

}

int fenerzhizhi(int low, int high) {

if(low == high) {

// cout << "第" <<++count << "次"<< endl;

// cout << "返回a[" << low <<"]" << a[low]<<endl;

return a[low];

}

int mid = (low + high) / 2;

// cout << "左分治"<<low << mid <<endl;

int x1 = fenerzhizhi(low, mid);

// cout << "右分治"<<mid+ 1 << high <<endl;

int x2 = fenerzhizhi(mid + 1, high);

int x3 = hebing(low, mid, high);

// cout << "第" <<++count << "次"<< endl;

// cout <<"x1:"<< x1 << endl <<"x2:"<< x2 << endl <<"x3"<< x3 <<endl;

return max(x1, max(x2, x3));

}

int main(){

char c;

int cnt = 0;

string s;

getline(cin, s);

istringstream is(s);

while(is >> a[cnt++]){

is >> c;

}

cnt-=2; //如果输入五个数字此时cnt = 7

cout << fenerzhizhi(0, cnt);

return 0;

}

发表于 2024-01-31 18:44:38 回复(1)

长琴搞事

s = input()
x = list(map(int, s.split(",")))

if not x:
    print(0)
lm, gm = 0, x[0]
for v in x:
    lm += v
    if lm > gm:
        gm = lm
    if lm < 0:
        lm = 0
        
print(gm)

发表于 2023-01-07 20:54:38 回复(0)

牛客575394749号

num =list(map(int,input().strip().split(',')))
maxn = 0
i = 1
dp = []
dp.append(num[0])
while i < len(num):
dp.append(max(dp[i-1]+num[i], num[i]))
maxn = max(maxn, dp[i])
i = i + 1

print(maxn)

想知道错在哪，有测试用例没通过

发表于 2022-02-11 21:48:08 回复(0)

OfferOffer你要去哪里呀

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

int main() {
    int x,  ans = INT_MIN, sum = 0;
    char c = '0';
    do {
        while(c == ' '){
            c = getchar();
        }
        cin >> x;
        sum += x;
        ans = max(ans, sum);
        if (sum < 0) {
            sum = 0;
        }
        c = getchar();
    }while(c != '\n');
    cout << ans << endl;
    return 0;
}

滑动窗口

发表于 2022-01-16 23:09:54 回复(0)

Python

maoxiaomao

A=list(map(int,input().strip().split(',')))
dp=[0]*len(A)
dp[0]=A[0]
barray=dp[0]                           #存储边界最大
for i in range(1,len(A)):
    pre=dp[i-1]
    after=sum(A[0:i+1])    
    if barray+A[i]>A[i]:  
        barray=barray+A[i]
    else:
        barray=A[i]
    after2=barray
    if pre>after and pre>after2:      #A[0...i]最大
        dp[i]=pre
    elif after>pre and after>after2:  #A[0...i i+1]最大
        dp[i]=after
    else:                             #A[..x..i+1]最大
        dp[i]=after2
print(dp[-1])

发表于 2021-05-24 18:51:51 回复(0)

MostTime

大一学生写写算法，算法比较简单，

先将a[i]转换成前缀和数列a[i],则求a[i]+...+a[j]转化成 a[j]-a[i-1], 求最大a[i]+...+a[j]转化求大a[j]-a[i-1]差

用b[i]记录a[i]前（不含a[i]）的最小值，

则枚举每个a[i]-b[i]保留最大值即为答案

#include <bits/stdc++.h>
#define N 10000005
#define f( i, a ,b) for(int i=(a);i<=(b);i++)
#define inf 1<<30
#define llo long long
using namespace std;
llo a[N],p,b[N],ans=-inf;int n=1;
 int main()
 {
    while (scanf("%lld",&a[n])!=EOF)
    {
        n++;
        char ch=getchar();
        if (ch!=','&&ch!=' ')
            break ;
    }n--;
    f(i,1,n)
        a[i]+=a[i-1];
     f(i,1,n)
        b[i]=p,p=min(p,a[i]);
    f(i,1,n)
         ans=max( ans,a[i]-b[i]);
     printf("%lld",ans);
     return 0;
 }

事实上困扰我的还是读入问题因为没给n的值也没结束符号不知道怎么处理。

发表于 2021-04-21 22:08:32 回复(0)