杭電ACM1003

其實(shí)就是簡單的子串序列和為最大值的問題，這里采用動態(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，這是因?yàn)轭}目要求是N的取值范圍是-1000 ~ 1000，所以在這里取max最大值為-1001。