HDU 1003

题意

给出一个乱序数组, 求一个区间使得区间内的数字之和最大
输出最大和, 区间开始位置, 结束位置

思路

经典dp
由于是从前往后更新, 所以用一个dp数组就可以处理
递推关系 : 如果dp[i-1] < 0 说明前面的和是小于0的, 此时更新开始位置(mrk)标记为当前位置
如果dp[i-1] >= 0 ,更新为 dp[i] = dp[i] + dp[i-1];
每次更新完dp[i]时要与当前最大和(mmax)比较, 以此更新最大和以及区间的开始(st), 结束(st)位置

AC代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

#define INF 0x3f3f3f3f
const int maxn = 100000+10;
int dp[maxn];

int main()
{
    int T, n, mrk, st, ed, mmax;
    cin >> T;
    for( int kase = 1; kase <= T; kase++ ){
        cin >> n;
        for( int i = 1; i <= n; i++ )
            cin >> dp[i];
        mrk = 1, st = 1, ed = 1, mmax = dp[1];
        for( int i = 2; i <= n; i++ ){
            if( dp[i-1] >= 0 )  dp[i] = dp[i-1] + dp[i];
            else mrk = i;
            if( dp[i] > mmax ){
                mmax = dp[i];
                st = mrk;
                ed = i;
            }
        }
        if( kase != 1 ) cout << '
';
        cout << "Case " << kase << ":
";
        cout << mmax << ' ' << st << ' ' << ed << '
';
    }
    return 0;
}