杭電ACM1003
其實就是簡單的子串序列和為最大值的問題卓舵，這里采用動態(tài)規(guī)劃法解決這個問題馍刮，代碼如下：
#include <iostream>
using namespace std;
int main()
{
int T, N, sum, max, a, i, j, l, z, r;
cin >> T;
for(i = 0; i < T; i++)
{
cin >> N;
for(l = z = r = sum = 0, max = -1001, j = 0; j < N; j++)
{
cin >> a;
sum += a;
if(max < sum)
{
l = z;
r = j;
max = sum;
}
if(sum < 0)
{
z = j + 1;
sum = 0;
}
}
cout << "Case " << i + 1 << ":" << endl;
cout <<max << " " << l + 1 << " " << r + 1 << endl;
if(i < T - 1)
cout << endl;
}
return 0;
}
唯一可能有疑問的是為什么max的初始值要設(shè)為-1001囱修，這是因為題目要求是N的取值范圍是-1000 ~ 1000，所以在這里取max最大值為-1001羊瘩。
