洛谷P1115 最大子段和 題解

題目描述

最大子段和是一道經典的動態規劃問題。題目要求：給定一個包含n個整數的序列，找出其中和最大的連續子序列，并輸出該最大和。若所有數均為負數，則取最大的那個數。

輸入格式：

• 第一行一個整數n（1 ≤ n ≤ 2×10?）
• 第二行n個整數a?,a?,…,a?（-10? ≤ a? ≤ 10?）

輸出格式：

• 輸出一個整數，表示最大子段和

樣例輸入：

5
-2 11 -4 13 -5 -2

樣例輸出：

20

（對應子序列[11,-4,13]）

解題思路

1. 動態規劃（Kadane算法）

核心思想：維護兩個關鍵變量

• current_sum：以當前元素結尾的最大子段和
• max_sum：全局最大子段和

狀態轉移方程：
$$current\_sum=\{\begin{array}{ll}{a}_i& \text{if?}current\_sum<0\\ current\_sum+a_i& \text{otherwise}\end{array}$$
$$max\_sum=\max (max\_sum,current\_sum)$$

2. 算法流程

1. 初始化current_sum = 0，max_sum = -∞
2. 遍歷數組中的每個元素：
   • 如果current_sum < 0，說明之前累計的和為負數，應舍棄，從當前元素重新開始
   • 否則，將當前元素加入累計和
   • 每次更新全局最大值max_sum
3. 最終max_sum即為答案

代碼解析

#include<bits/stdc++.h>
using namespace std;int main() {long long sum = 0;         // 當前子段和int x;                     // 臨時存儲輸入值int n;cin >> n;// 初始化最大值為最小可能的long long值long long maxx = 0xffffffffffff;maxx *= -1;               // 等價于 LLONG_MINfor (int i = 1; i <= n; ++i) {cin >> x;if (sum > 0) {        // 累計和為正，繼續擴展子段sum += x;maxx = max(maxx, sum);} else {              // 累計和為負，重新開始sum = x;maxx = max(maxx, sum);}}cout << maxx;return 0;
}

關鍵點說明

1. 初始值設置：

   • maxx初始化為0xffffffffffff * -1，等價于-2^48，確保能正確處理全負數情況
   • 更規范的寫法是使用#include <climits>中的LLONG_MIN

2. 決策邏輯：

   • 當sum > 0時，繼續累加當前元素可能獲得更大和
   • 當sum ≤ 0時，舍棄之前所有元素，從當前元素重新開始

3. 時間復雜度：O(n)

   • 僅需一次線性掃描即可完成計算

復雜度分析

指標	復雜度	說明
時間復雜度	O(n)	單次遍歷數組
空間復雜度	O(1)	僅使用常數級額外空間

邊界情況測試

測試用例	預期輸出	實際輸出	說明
1 -5	-5	-5	單個負數元素
3 -1 -2 -3	-1	-1	全負數序列
4 1 2 -3 4	6	6	包含負數的中間最優子段
5 -2 11 -4 13 -5 -2	20	20	經典樣例

優化方向

1. 輸入優化：

   • 使用scanf/printf替代cin/cout可提升IO速度
   • 添加ios::sync_with_stdio(false)加速C++流

2. 代碼簡化：

   // 簡化版代碼（功能完全等價）
   #include<bits/stdc++.h>
   using namespace std;
   int main() {int n, x;cin >> n;long long sum = 0, maxx = LLONG_MIN;while(n--) {cin >> x;sum = max((long long)x, sum + x);maxx = max(maxx, sum);}cout << maxx;return 0;
   }
   

總結

本題是動態規劃的經典入門題，Kadane算法通過O(n)時間復雜度和O(1)空間復雜度完美解決問題。理解"舍棄負貢獻"的核心思想是關鍵，這種貪心策略在許多序列問題中都有廣泛應用。實際編碼時需特別注意全負數等邊界情況的處理。