首页 > 代码库 > hdu 1003

hdu 1003

题意 :求最大子段和 并且输出起始位置

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
using namespace std;
int main()
{int N,n,a[100001],first,last;
 cin>>N;
 for(int i=1;i<=N;i++)
 {
     cin>>n;
     for(int j=1;j<=n;j++)
         cin>>a[j];
     int max=-1000,sum=0,k=1;
     for(j=1;j<=n;j++)
     {
         sum=sum+a[j];
         if(sum>max)//如果当前的最大值大于以前的最大值  更新 sum 与max 都是一种计算的结果和属性相同
         {
         first=k;
         last=j;
         max=sum;
         }
         if(sum<0)
         {
             k=j+1;
             sum=0;
         }
     }
     cout<<"Case "<<i<<":"<<endl;
     cout<<max<<" "<<first<<" "<<last;
     if(i==N)
         cout<<endl;
     else
         cout<<endl<<endl;
 }
 return 0;
}