（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

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

这就是模板题目，可能。需要注意就是在头节点的更换上面，不能在每一次更新最大字段和的时候就更新头head，很重要，需要更换头节点的时候必须满足ans>sum(ans为当前位置向前的最大字段，sum为这个位置之前的最大子段和) 的时候。这就需要用一个temp来保存当sum需要更换的时候的头节点变化。

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];
        int ans=aa[1],temp=1,head=1,tail=1;
        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){
                head=temp;
                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

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];
        int ans=aa[1],temp=1,head=1,tail=1;
        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){
                head=temp;
                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;
}