最大子数组和

情景导入

有时，我们需要求一个数组的最大子数组和（即连续子数组的和最大），并给出这个和（别问为什么，问就是题目要）。

Kadane 算法的原理

首先，我们获得一个数组，并定义两个变量 csum 和 smax 。
然后，我们可以开始 kadane 算法。

在算法开始时，将 csum（当前连续子段的和）初始化为数组的第一个元素，将 smax（全局最大子段和）也初始化为该值。
接下来，从第二个元素开始，依次向右遍历整个数组。

对于每一个元素 a[i]，我们要判断：
如果当前的 csum 加上 a[i] 小于 a[i] （ csum 小于 0），说明前面的子段对总和是负贡献，继续加下去只会让后续的结果更小，所以应当舍弃之前的子段，从当前位置重新开始，也就是令 csum = a[i]。
否则，如果 csum 仍然大于等于 0，就说明它对后续仍有正向贡献，我们可以安全地把当前元素加上去，csum += a[i]。

每处理完一个元素，就更新全局最大值：
smax = max(smax, csum)。
这样，smax 始终保存着从开头到当前位置为止出现过的最大连续子段和。

当遍历完整个数组后，smax 就是整个数组的最大连续子段和。

换句话说，Kadane 算法的核心思想是：
只要当前子段的和为负，就立即丢弃，从当前位置重新开始。
它把一个看似需要枚举所有区间的问题，优化成了线性时间的动态更新过程。

视频（点击观看）：

点击观看这个前摇过长的视频（bushi

示例题目

【题目描述】

给定一个只包含 '0' 和 '1' 的字符串，你可以选择恰好一个连续子串，将其中的字符全部反转（即 '0' 变 '1'，'1' 变 '0'）。
你的任务是，在最多一次这样的操作之后，使得整个字符串中 '1' 的数量尽可能多。

输出操作后 '1' 的最大可能数量。

【输入格式】

一行，一个长度为 n (1 ≤ n ≤ 2×10^5) 的字符串，只包含字符 '0' 和 '1'。

【输出格式】

一个整数，表示翻转后 '1' 的最大数量。

样例

【样例输入 1】

1
110001

【样例输出 1】

1
6

【样例解释 1】

原本有 3 个 '1'。
翻转中间的 "000" → "111"，变为 "111111"，此时共有 6 个 '1'，但我们不能再优化了。
输出 6。

【样例输入 2】

1
1111

【样例输出 2】

1
4

【样例解释 2】

原本全是 '1'，翻转任何一段都会减少 '1'，所以最优是不操作。

【数据范围与提示】

  • 1 ≤ n ≤ 200000
  • 字符仅含 '0' 和 '1'

暴力做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();
    int max_ones = 0;

    // 先统计原本有多少个1
    for (char c : str) if (c == '1') max_ones++;

    int ans = max_ones; // 记录最大结果

    // 暴力枚举区间 [l, r]
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            int now = max_ones;

            // 模拟反转区间
            for (int i = l; i <= r; i++) {
                if (str[i] == '1') now--; // 被反转成0
                else now++;              // 被反转成1
            }

            ans = max(ans, now);
        }
    }

    cout << ans << "\n";
    return 0;
}

这种做法的时间复杂度是 O(n³) ，数据一大就 T 了

kadane 做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 2e5 + 5, inf = INT_MIN;

int a[N], m, c, one;
// a是数组（只有"1"和"-1"），m是中转，one是原始字符串所有1的个数
int csum = inf, smax = inf;// 其实完全没必要，但是良好习惯（强迫症（bushi

int main() {
    // 
    string str;
    cin >> str;
    int len = str.size();// 降低复杂度，每次调用 str.size() 的复杂度是 O(n)
    for (int i = 0;i < len;i++) {
        int m = str[i] - '0';
        // 我也不知道为什么要写一个m，当我写完这个代码的时候才反应过来不用写m，懒得改了。这样还更明确
        if (m == 1)a[i] = -1, one++;
        else a[i] = 1;
        // 如果是1，数组的那一位变成-1，不是就变成1.因为我们要尽可能少的翻转1，尽可能多的翻转0，这样写用kadane的时候就能直接套进去，翻转尽可能多的0。
    }
    csum = a[0], smax = a[0];
    // 一个是记录当前选中连续子区间的和（用来比较是否需要放弃），一个是用来记录历史子区间最大和
    for (int i = 1;i < c;i++) {
        if (csum < 0) {// csum + a[i] < a[i] 等价于 csum < 0
            csum = a[i];// 如果是就放弃，重新开始
        }
        else {
            csum += a[i];// 否则就继续累加
        }
        smax = max(csum, smax);// 维护最大值
    }
    if (one == len)cout << one;// 如果全是1，直接输出长度
    else cout << one + smax;
    // 否则输出转换出来的1（即kadane算法算出来的最大子区间和，这也是为什么我要定为"1"和"-1"。这里的1是减去了翻转区间中变成0的那些，所以后面可以直接加原始字符串1的个数）加原始字符串中1的个数。
    return 0;// 完结撒花 *★,°*:.☆(￣▽￣)/$:*.°★* 。
}

注释已经写得非常明确了，有不懂的可以在评论区提出疑问，我看到后会尽量在第一时间解答