（HDU – 1003 ）Max Sum(（HDU – 1003 ）Max Sum)-其他

（HDU – 1003 ）Max Sum(（HDU – 1003 ）Max Sum)

Input

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).Output

For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

``````2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
``````
``````Case 1:
14 1 4

Case 2:
7 1 6``````

AC代码：

``````#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int dp[N],aa[N];

int main(){
int t,num=0,n;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>aa[i];
for(int i=1;i<=n;i++){
if(dp[i-1]+aa[i]<aa[i]) temp=i;
dp[i]=max(dp[i-1]+aa[i],aa[i]);
if(dp[i]>ans){
tail=i;
}
ans=max(ans,dp[i]);
}
printf("Case %d:\n%d %d %d\n",++num,ans,head,tail);
if(t)cout<<endl;
}
return 0;
}``````
————————

Input

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).Output

For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

``````2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
``````
``````Case 1:
14 1 4

Case 2:
7 1 6``````

This is the title of the template, maybe. It should be noted that for the replacement of header nodes, the header cannot be updated every time the maximum field sum is updated. It is very important that ans & gt; Sum (ANS is the largest field forward of the current position, and sum is the sum of the largest sub segments before this position). This requires a temp to save the changes of the head node when the sum needs to be replaced.

AC Code:

``````#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int dp[N],aa[N];

int main(){
int t,num=0,n;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>aa[i];
for(int i=1;i<=n;i++){
if(dp[i-1]+aa[i]<aa[i]) temp=i;
dp[i]=max(dp[i-1]+aa[i],aa[i]);
if(dp[i]>ans){