题意 ：求最大子段和 并且输出起始位置
|
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;} |
原文：http://www.cnblogs.com/zhangdashuai/p/3704456.html