最大子段和问题：从暴力法到优化的算法解析

最大子段和问题：从暴力法到优化的算法解析

题目链接

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式

• 第一行是一个整数，表示序列的长度 n。
• 第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1：

7 2 -4 3 -1 2 -4 3 

输出 #1：

4 

样例解释：

选取子数组 {3, −1, 2}，其和为 4。

数据规模与约定

• 对于 40% 的数据，保证 n ≤ 2 × 10³。
• 对于 100% 的数据，保证 1 ≤ n ≤ 2 × 10⁵，且 −10⁴ ≤ ai ≤ 10⁴。

---

算法解析：从暴力法到优化的全面分析

本问题的核心是求解一个数组中 连续子数组 的最大和。为了帮助大家更好地理解如何优化算法，我们将从最基础的暴力法出发，逐步介绍一些优化策略，最后给出最优解法。每一种算法都有其优点和局限，适用于不同规模的数据。

---

第一步：暴力法（最直观的解法）

暴力法的基本思路非常简单：枚举数组中所有可能的子数组，计算它们的和，并找出最大的那个子数组和。

步骤：

1. 对于每个子数组的起始位置 i，遍历所有可能的结束位置 j。
2. 计算子数组 a[i]…a[j] 的和。
3. 不断更新最大子数组和。

代码实现：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n]; // 输入数组
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ret = INT_MIN; // 暴力法：枚举所有子数组
    for (int i = 0; i < n; i++) {
         sum = ;
         ( j = i; j < n; j++) {
            sum += a[j]; 
            ret = (ret, sum); 
        }
    }
    cout << ret << endl; 
     ;
}