很基本的DP，复杂度为O（N）
#include<iostream>
#include<cstdio>
using namespace std;
int arr[100010];
struct node
{
int v,head;
}dp[100010];
int head,rear;
int function(int n)
{
int ans=0;
dp[1].v=arr[1];
dp[1].head=1;
for(int i=2;i<=n;i++)
{
if(dp[i-1].v>=0)
{
dp[i].v=dp[i-1].v+arr[i];
dp[i].head=dp[i-1].head;
}
else
{
dp[i].v=arr[i];
dp[i].head=i;
}
}
for(int i=1;i<=n;i++)
if(ans<dp[i].v)
{
ans=dp[i].v;
head=dp[i].head;
rear=i;
}
return ans;
}
int main()
{
int n,c;
scanf("%d",&c);
for(int j=1;j<=c;j++)
{
int num=0,ans=-2000;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
if(arr[i]<=0)
{
num++;
}
}
if(num==n)
{
for(int i=1;i<=n;i++)
{
if(arr[i]>ans)
{
ans=arr[i];
head=rear=i;
}
}
}
else
{
ans=function(n);
}
if(j==c)
{
printf("Case %d:\n",j);
printf("%d %d %d\n",ans,head,rear);
}
else
{
printf("Case %d:\n",j);
printf("%d %d %d\n\n",ans,head,rear);
}
}
//system("pause");
return 0;
}