HDU 1003 Max Sum：最大子段和與區間端點輸出

題目大意

給定長度 N (≤ 100,000) 的整數序列（元素值在 [-1000, 1000]），求最大子段和，並輸出該子段的起始和結束位置（1-based）。若有多解，輸出起始位置最小、再終止位置最小的一組。多組測試資料，輸出格式要求空行分隔。

動態規劃 / Kadane 算法

維護 now 為以當前位置結尾的最大子段和，maxSum 為全局最大值。同時記錄 start、end 及當前子段的起始點 curStart。

• 若 now + a[i] < a[i]，說明以 i 為新起點更好，更新 now = a[i]，curStart = i。
• 否則 now += a[i]。
• 若 maxSum，更新 maxSum、start = curStart、end = i。

參考代碼 (C++)

#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n; scanf("%d", &n);
        int maxSum = -INF, now = 0;
        int start = 1, end = 1, curStart = 1;
        for (int i = 1; i <= n; ++i) {
            int x; scanf("%d", &x);
            if (now + x < x) { now = x; curStart = i; }
            else now += x;
            if (now > maxSum) {
                maxSum = now;
                start = curStart;
                end = i;
            }
        }
        printf("Case %d:\n%d %d %d\n", cas, maxSum, start, end);
        if (cas != T) printf("\n");
    }
    return 0;
}

複雜度

時間 O(N)，空間 O(1)，完美通過大數據限制。