kadane算法

你好！还没学过 Kadane 算法没关系，这正是你从“暴力模拟”转向“动态规划（DP）”思维的最好契机。

作为教练，我不会直接给你干巴巴的公式，我们先在草稿纸上玩一个**“贪心小游戏”**，玩懂了，你就掌握了这个 $O(n)$ 的神级算法。

一、 核心问题： contiguous（连续）

Kadane 算法解决的是：“给定一个数组，求其中和最大的【连续】子数组。”

暴力想法：枚举起点 $i$，枚举终点 $j$，算出中间的和。复杂度 $O(n^2)$。当 $n=10^5$ 时，必炸。 Kadane 想法：我能不能只走一遍数组（$O(n)$）就知道答案？

二、 启发式推导：及时止损

想象你在一条路上走，脚下每一步都有金币（正数）或者坑（负数）。你的目标是：走出一段距离，让你手里的金币总数最多。

现在你走到了第 $i$ 步，手里已经攒了一堆金币（记为 current_sum）。面对当前地上的数字 x，你面临两个选择：

1. 继续带着以前的累积：把 x 捡起来，带着之前的家底继续走（current_sum + x）。
2. 原地止损，重新开始：把以前攒的（可能是负数，拖了后腿）全部扔掉，从当前的 x 重新开始计算（x）。

你的决策逻辑： 如果 current_sum + x 还没 x 本身大，那前面的累积就是“负资产”，扔了它！

三、 算法的数学表达（DP 状态）

我们定义 $dp[i]$ 为：以第 $i$ 个元素【结尾】的最大子数组和。

为什么一定要“以 $i$ 结尾”？ 因为子数组必须是连续的。如果我们知道了 $dp[i-1]$，那么 $dp[i]$ 只有两种可能：

1. 跟在 $i-1$ 后面：$dp[i-1] + nums[i]$
2. 自己另起炉灶：$nums[i]$

状态转移方程：

最后，整个数组的最大子数组和，就是所有 $dp[i]$ 里的最大值。

四、 图形推演过程

假设数组为：[-2, 1, -3, 4, -1, 2, 1, -5, 4]

结果： 最大和是 6，对应的子数组是 [4, -1, 2, 1]。

五、 为什么环形题目需要它？

回到你之前问的那道环形题目。环形数组的最大子数组和有两种情况：

1. 不跨越首尾：这就是原汁原味的 Kadane 算法。
2. 跨越首尾：
   • 这时候，我们要选头一段和尾一段。
   • 等价于：总和减去中间的一段。
   • 要让剩下的两头最大，就要让中间被减去的那段最小。
   • 于是：我们再次使用 Kadane 算法，只不过这次是求最小子数组和。

六、 总结：读题时的思维锚点

在 NOI 竞赛中，只要看到以下描述，请条件反射想到 Kadane：

• 关键词：“连续”、“子段”、“最大和”。
• 复杂度要求：$O(n)$。
• 变化形：
  • 如果是环形 $\rightarrow$ 考虑“总和 - 最小子段”。
  • 如果限制长度 $\rightarrow$ 考虑“单调队列优化 Kadane”。

教练寄语：Kadane 算法是动态规划中最优美、最精炼的逻辑之一。它告诉我们：如果过去成为了负担，最好的选择就是放下过去，从现在重新开始。

现在，试着回去看那份数据生成器和标准代码，看看那两个 max 和 min 的循环，是不是瞬间清晰了？加油！

作为教练，制作环形子数组最大和的测试数据时，核心在于构造能够覆盖“线性最大和”、“环形最大和”以及“全负数边界”这三种逻辑路径的数据。

本题的时间复杂度要求为 $O(N)$，因此我们的数据生成器和标准答案程序都必须严格遵守线性时间复杂度。虽然本题不涉及除法运算，但我们在逻辑实现上会保持严谨，确保不会出现任何运行时异常。

一、 数据生成器代码 (C++14)

该程序采用非递归逻辑，通过模拟标准算法生成对应的 .out 文件。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>

using namespace std;

typedef long long ll;

// 标程逻辑，严格对齐官方
ll get_ans(int n, const vector<int>& a) {
    ll total = 0, maxS = -2e18, curMax = 0, minS = 2e18, curMin = 0;
    for (int x : a) {
        total += x;
        curMax = max((ll)x, curMax + x);
        maxS = max(maxS, curMax);
        curMin = min((ll)x, curMin + x);
        minS = min(minS, curMin);
    }
    return (maxS < 0) ? maxS : max(maxS, total - minS);
}

void gen(int id, int n, vector<int> a) {
    ofstream fout(to_string(id) + ".in");
    fout << n << "\n";
    for(int i=0; i<n; ++i) fout << a[i] << (i==n-1?"":" ");
    fout << endl;
    
    ofstream fans(to_string(id) + ".out");
    fans << get_ans(n, a) << endl;
    cout << "Case " << id << " generated." << endl;
}

int main() {
    mt19937 rng(time(0));
    
    // Case 1-3: 严格遵循 LeetCode 官方样例
    gen(1, 4, {1, -2, 3, -2});
    gen(2, 3, {5, -3, 5});
    gen(3, 4, {3, -2, 2, -3});
    
    // Case 4: 全负数特判
    gen(4, 3, {-3, -2, -3});
    
    // Case 5: 只有一个元素
    gen(5, 1, {10});
    
    // Case 6: 线性最大胜出 (中间极大)
    gen(6, 5, {-10, -10, 50, -10, -10});
    
    // Case 7: 环形最大胜出 (两头极大)
    gen(7, 5, {20, -50, -50, -50, 20});
    
    // Case 8-10: 极限规模随机
    for(int i=8; i<=10; ++i) {
        int n = 30000;
        vector<int> a(n);
        for(int j=0; j<n; ++j) a[j] = (int)(rng() % 60001 - 30000);
        gen(i, n, a);
    }
    return 0;
}

二、 测试点设计思路（创建 OJ 评测点参考）

作为教练，我们需要通过以下维度来检测选手代码的鲁棒性：

三、 考场避坑建议

1. 关于除零异常： 本题不涉及除法。但在处理环形下标（如 (i+1)%n）时，若选手误用 $n$ 做除数且未判断 $n=0$（虽然本题 $n \ge 1$），可能导致风险。生成器已确保 $n \ge 1$。
2. 关于“空子数组”问题： 这是本题最大的陷阱。如果数组全为 [-1, -2, -3]，线性最大和是 -1。如果不加判断使用 total_sum - min_sum，会得到 -6 - (-6) = 0。但 0 代表的是不选任何元素的空子数组，不符合题目“非空”要求。必须在代码中判断 max_so_far < 0。
3. 数值范围： 虽然 $30000^2$ 在 int 范围内，但如果数组长度进一步扩大，累加和会轻松溢出。在 NOI 竞赛中，只要涉及求和，请无脑使用 long long。
4. 非递归安全： 本生成器和算法完全基于迭代（Loops），不涉及任何递归调用，即便在系统栈空间极其有限的评测环境下也能稳定运行，绝无爆栈风险。

这份生成器生成的 .in 和 .out 文件格式严谨，可以直接用于创建练习赛。加油！

你好，同学。这道题是动态规划中 Kadane 算法 的高级变体。在 NOI 竞赛中，它不仅考察你对基础 DP 的理解，还考察你对 “正难则反”（补集思想）的灵活运用。

以下是基于 C++14 标准 的满分题解代码。

一、 环形子数组最大和 标准题解 (C++14)

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

using namespace std;

/**
 * 题目：环形子数组最大和
 * 核心思路：分类讨论
 * 1. 最大子数组不跨越首尾：直接使用 Kadane 算法求线性数组的最大子数组和 (max_sum)。
 * 2. 最大子数组跨越首尾：这意味着数组中间有一段连续的子数组被“剩下了”。
 *    要让跨越首尾的和最大，只需让剩下的中间那段连续子数组的和最小 (min_sum)。
 *    跨越首尾的最大和 = 总和 (total_sum) - 最小子数组和 (min_sum)。
 */

void solve() {
    int n;
    if (!(cin >> n)) return;

    // 考虑到数据规模和求和，使用 long long 防止计算过程中产生溢出是一个好习惯
    long long total_sum = 0;
    long long cur_max = 0, max_so_far = -3e9; // 初始设为极小值
    long long cur_min = 0, min_so_far = 3e9;  // 初始设为极大值

    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        total_sum += x;

        // 1. 标准 Kadane 算法求最大子数组和
        cur_max = max(x, cur_max + x);
        max_so_far = max(max_so_far, cur_max);

        // 2. 变体 Kadane 算法求最小子数组和
        cur_min = min(x, cur_min + x);
        min_so_far = min(min_so_far, cur_min);
    }

    /* 
     * 关键易错点处理：
     * 如果 max_so_far < 0，说明数组中所有的数都是负数。
     * 此时，total_sum == min_so_far (最小子数组就是整个数组)，
     * total_sum - min_so_far 会得到 0，这代表一个“空子数组”。
     * 但题目要求是非空子数组，所以全负数情况下直接返回 max_so_far（即最大的那个负数）。
     */
    if (max_so_far < 0) {
        cout << max_so_far << endl;
    } else {
        // 返回“不跨越首尾”和“跨越首尾”两种情况中的较大值
        cout << max(max_so_far, total_sum - min_so_far) << endl;
    }
}

int main() {
    // NOI 竞赛必备：极大提升 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度：$O(n)$

• 推导过程：我们对长度为 $n$ 的数组进行了仅有的一趟 for 循环遍历。在每一轮迭代中，我们只进行了常数次的加法和 max/min 比较操作。
• 结论：总时间复杂度为 $O(n)$。在 $n = 3 \times 10^4$ 的规模下，执行时间远小于 1ms，即使 $n$ 增加到 $10^6$ 也能轻松应对。

2. 空间复杂度：$O(1)$

• 推导过程：除了存储输入数据的必要空间（如果在循环中边读边处理，甚至可以不用 vector），我们只定义了 total_sum, max_so_far, min_so_far 等有限的几个变量。
• 结论：额外空间复杂度为 $O(1)$。

三、 考场避坑与优化建议

1. 易错点：全负数情况

这是本题最经典的一个坑。

• 现象：假设数组是 [-3, -2, -3]。
  • max_so_far 会得到 -2。
  • total_sum 是 -8，min_so_far 也是 -8。
  • total_sum - min_so_far = 0。
• 纠正：由于题目要求子数组非空，所以我们不能选出“空集”得到的 0。当最大的数也是负数时，必须直接输出这个负数。

2. 时间优化建议

• 快读 (Fast I/O)：虽然本题 $n$ 只有 $3 \times 10^4$，但如果是在 $n=10^6$ 的正式 NOI 题目中，请务必使用 ios::sync_with_stdio(false); cin.tie(0); 或者手写 getchar() 版本的快读。
• 单次遍历：本题可以在读入每个数的同时更新所有 DP 状态，不需要开数组存下来再跑第二次循环。

3. 数值溢出

• 建议：虽然本题 $n \times |nums[i]|$ 的最大值约为 $9 \times 10^8$，未超过 int 的 $2 \times 10^9$ 限制。但在 NOI 考场上，处理所有累加和、积、差的操作时，首选 long long。这能帮你避开 50% 以上的非算法性失分。

教练总结：这道题是补集思想的典型应用。当我们难以直接计算“跨越边界”的连续部分时，通过计算“被剩下的中间部分”来间接求解，是一种非常高级的思维跃迁。去实现它吧！