ICPC成都站补题复盘：从超时到AC，我的优化血泪史

在刚结束不久的24ICPC成都站比赛中，虽然未能取得理想成绩，但是赛后补题的过程受益匪浅。其中一道题，最初提交时频频超时，经过多轮优化最终成功通过。本文将以此题为例，详细记录整个优化过程，希望能给各位带来一些启发。

问题场景重现

题目大致描述（这里简化方便说明）：给定一个包含N个整数的数组，要求计算所有子数组的和，并返回这些和中最大的一个。N的范围是1 <= N <= 10^6，数组中的元素范围是 -10^3 <= element <= 10^3。 简单的暴力解法就是遍历所有子数组，计算和并取最大值，但显然时间复杂度为O(N^2)，对于10^6的数据规模，必然超时。

暴力解法的超时分析

最开始的思路就是暴力枚举，代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;

  vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }

  long long max_sum = -1e18; // 初始化为极小值
  for (int i = 0; i < n; ++i) {
    long long current_sum = 0;
    for (int j = i; j < n; ++j) {
      current_sum += arr[j];
      max_sum = max(max_sum, current_sum);
    }
  }

  cout << max_sum << endl;

  return 0;
}

很明显，这段代码的时间复杂度是O(N^2)。在N等于10^6的情况下，计算次数将达到10^12级别，远远超过了比赛通常允许的1秒或2秒的时间限制。 考虑到服务器 CPU 频率的差异，以及编译器的优化程度，这种复杂度的算法基本没有通过的可能性。需要寻找更优的解决方案。

Kadane算法：O(N)时间复杂度的解决方案

解决这类最大子数组和问题，可以使用著名的Kadane算法，它能够将时间复杂度降到O(N)。其核心思想是动态规划：

• 定义max_so_far：到目前为止的最大子数组和。
• 定义current_max：以当前元素结尾的最大子数组和。
• 遍历数组，对于每个元素，current_max要么是当前元素本身，要么是current_max + 当前元素，取两者中的较大值。
• 每次更新current_max后，用它来更新max_so_far。

Kadane算法的关键在于，它避免了重复计算子数组的和，而是通过递推的方式，利用之前计算的结果。这样就能在线性时间内找到最大子数组和。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;

  vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }

  long long max_so_far = -1e18; // 初始化为极小值
  long long current_max = 0;

  for (int i = 0; i < n; ++i) {
    current_max = max((long long)arr[i], current_max + arr[i]); // 关键步骤：要么从当前元素开始，要么延续之前的子数组
    max_so_far = max(max_so_far, current_max); // 更新全局最大值
  }

  cout << max_so_far << endl;

  return 0;
}

这段代码的时间复杂度为O(N)，在10^6的数据规模下，能够快速计算出结果。使用Kadane算法后，成功解决了超时问题。

实战避坑经验

• 数据类型选择： 注意到题目中元素的范围是 -10^3 <= element <= 10^3，N的范围是1 <= N <= 10^6。因此，子数组和的最大值可能达到 10^9 级别。int类型可能会溢出，所以需要使用long long类型。
• 初始化： max_so_far 必须初始化为一个足够小的负数，确保即使所有元素都是负数，也能得到正确的结果。如果初始化为0，当所有元素都是负数时，结果将是0，这是错误的。
• 边界情况： 需要考虑数组为空的情况。虽然题目中明确N >= 1，但在实际编程中，良好的习惯是考虑所有可能的边界情况，增加代码的健壮性。

总结

通过这次24ICPC成都站的补题经历，深刻体会到算法选择的重要性。从最初的暴力超时，到最终使用Kadane算法解决问题，不仅学习了新的算法，也巩固了数据类型选择、初始化等编程基础知识。希望这次经历能帮助各位在以后的编程竞赛中少走弯路。