题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1003
题目大意:
求最大子段和,并且输出最大子段和的起始位置和终止位置。
思路:
根据最大子段和基本方法,直接在线处理(如果对最大子段和不熟悉,点这里)
需要增加两个变量,start和finish,记录最大子段和的起点和终点。如果thissum > maxsum,更新这三个值。如果thissum < 0,设置thissum = 0,并且thisstart = i + 1,因为thissum<0时包括了第i个数字,可推出第i个数一定是负数,那thisstart肯定要先设置成下一个i。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
const int INF = <<;
int T, cases;
int n;
int main()
{
cin >> T;
while(T--)
{
cin >> n;
int thissum = , maxsum = -INF, start = , finish = , x;
int thisstart = ;
for(int i = ; i <= n; i++)
{
cin >> x;
thissum += x;
if(thissum > maxsum)
{
maxsum = thissum;
start = thisstart;
finish = i;
}
if(thissum < )
{
thissum = ;
thisstart = i + ;
}
}
printf("Case %d:\n", ++cases);
printf("%d %d %d\n", maxsum, start, finish);
if(T)cout<<endl;
}
return ;
}