算法题之Max Sum

文章目录

1. 1. 题目
2. 2. 解答
   1. 2.1. C语言实现
   2. 2.2. C++实现
   3. 2.3. Java实现

题目

杭电acm题目：http://acm.hdu.edu.cn/showproblem.php?pid=1003

解答

以下为在杭电hdu acm上已AC的C语言、C++和Java实现的三种方法

C语言实现

#include<stdio.h>
int a[100001];
int main()
{
    int t,c,b,i,s,n,m,max,k,j;
    scanf("%d",&t);
    for(k=1;k<=t;k++)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        max=-1000000;
        j=1;
        s=0;
        for(i=1;i<=n;i++)
        {
            s+=a[i];
            if(s>max)
            {
                max=s;
                c=j;
                b=i;
                
            }
            if(s<0)
            {
                s=0;
                j=i+1;
            }
            
            
        }
        printf("Case %d:\n%d %d %d\n",k,max,c,b);
        if(k<t)
            printf("\n");
    }
    return 0;
}

C++实现

#include<iostream>
using namespace std;
int main(){
    int i,j,k,h,g,t,n,sum,max;
    int a[100001];
    cin>>t;
    for(i=1;i<=t;i++){
        cin>>n;
        for(j=1;j<=n;j++)
            cin>>a[j];
        max=-1000000;
        sum=0;
        k=1;
        for(j=1;j<=n;j++){
            sum+=a[j];
            if(sum>max){
                max=sum;
                h=k;
                g=j;
            }
            if(sum<0){
                sum=0;
                k=j+1;
            }
        }
        cout<<"Case "<<i<<":"<<endl<<max<<" "<<h<<" "<<g<<endl;
        if(i<t){
            cout<<endl;
        }
    }
    return 0;
}

Java实现

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int i,j,t,n,k,h = 0,g = 0,sum,max;
        int a[]=new int[100001];
        Scanner scanner=new Scanner(System.in);
        t=scanner.nextInt();
        for(i=1;i<=t;i++){
            System.out.println("Case "+i+":");
            n=scanner.nextInt();
            for(j=1;j<=n;j++)
                a[j]=scanner.nextInt();
            max=-1000000;
            sum=0;
            k=1;
            for(j=1;j<=n;j++){
                sum+=a[j];
                if (sum>max) {
                    max=sum;
                    h=k;
                    g=j;
                }
                if (sum<0) {
                    sum=0;
                    k=j+1;
                }
            }
            System.out.println(max+" "+h+" "+g);
            if (i<t) {
                System.out.println();
            }
        }    
}