• 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 startswith a number N(1<=N<=100000), then N integers followed(all the integersare 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 linecontains three integers, the Max Sum in the sequence, the start position of thesub-sequence, the end position of the sub-sequence. If there are more than oneresult, output the first one. Output a blank line between two cases.
• Sample Input
• 2
• 5 6 -1 5 4 -7
• 7 0 6 -1 1 -6 7 -5
•
• Sample Output
• Case 1:
• 14 1 4
• Case 2:
7 1 6
给定由n个整数(可能为负整数)组成的序列A1,A2,A3,...,An,求该序列的连续子串的和的最大值。当所有整数均为负整数时定义其最大子串和为0
例如 {-2,11,-4,13,-5,-2} 的最大子串和为20
#include #include #include #include using namespace std; int main() { int n; int T; long long a[100005]; long long dp[100005]; scanf("%d",&T); for(int t=1; t<=T; t++) { scanf("%d",&n); for(int i=0; i =0) dp[i]=dp[i-1]+a[i]; else dp[i]=a[i]; } int start=0,end=0,ans=a[0]; for(int i=1; i =0; i--) { if (dp[i]>=0) start=i; else break; } printf("Case %d:\n",t); printf("%d %d %d\n",ans,start+1,end+1); if (t