游客 注册 | 登录
中文 | En

1914 - 最大连续和

通过次数

0

提交次数

0

时间限制 : 5 秒 内存限制 : 128 MB

给定一列数字A1，A2，A3...，An。求序列中一段连续的数字，使得它们的和最大。保证数字个数N≤1000，|Ai|≤10000。

题目输入

对于每组数据，第一行是正整数N，描述数字的个数。第二行有N个数字，按一定的顺序给出。输入以N=0结束。

题目输出

对于每组数据，输出最大连续和。

输入/输出样例

输入格式

3
-1 1 0
5
1 2 3 4 -5
0

输出格式

1
10

C++解答

#include <iostream>
using namespace std;
int b[1005], a[1005];
const int INF = 1000000000;
int main(){
    int n, MAX;
    while(cin >> n && n){
      b[0] = 0;
      MAX = -INF;
      for(int i = 1; i <= n; ++i){
        cin >> a[i];
        b[i] = a[i]+b[i-1];
      }
      for(int i = 0; i < n; ++i)
        for(int j = i+1; j <= n; ++j)
          if(b[j]-b[i] > MAX)
            MAX = b[j]-b[i];
      cout << MAX << endl;
    }
    return 0;
}

Java解答

import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            int n=in.nextInt();
            if(n==0) break;
            int a[]=new int[n];
            for(int i=0;i<n;i++){
                a[i]=in.nextInt();
            }
            int sum=a[0];
            for(int i=0;i<n;i++){
                if(a[i]>sum) sum=a[i];
            }
            for(int i=0;i<n;i++){
                for(int j=n-1;j>i;j--){
                    int add=a[i];
                    for(int k=i;k<j;k++){
                        add+=a[k+1];
                        if(add>=sum)
                            sum=add;
                    }
                }
            }
            System.out.println(sum);
        }
    }
}
请先登陆