算法-最大子段和

最大子段和

刷洛谷的题的时候学到的新知识点，算法描述为下：

概念描述

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

而这个其中最大的数字就是这个数组的 最大字段和

算法代码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int n, a[N];

int main()
{
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	long long ans = -1e9;
	long long cur = a[1];
	for (int i = 2;i <= n;i ++)
	{
		cur = max(cur + a[i], a[i] + 0LL);
		ans = max(cur, ans);
	}
	printf("%lld", ans);
	return 0;
}

代码解释：

我们通过记录两个变量来记录当前的最大字段和，使用 cur 来记录这个目前的子段和是多少，然后我们比较，当前是加上此数字后，来判断当前的结果和当前枚举到的数字的大小，也就是这个子段和如果不如当前数字一个数字的结果更优，我们就更新即可。然后使用 ans 来记录这个答案即可。

时间复杂度

$$
O(n)
$$

  • 因为我们只对数组进行一次遍历即可得出答案，所以我们的时间复杂度为 $O(n)$

例题展示

P1115 最大子段和 - 洛谷

模版题，直接看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int n, a[N];

int main()
{
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	long long ans = -1e9;
	long long cur = a[1];
	for (int i = 2;i <= n;i ++)
	{
		cur = max(cur + a[i], a[i] + 0LL);
		ans = max(cur, ans);
	}
	printf("%lld", ans);
	return 0;
}

P11642 【MX-X8-T1】「TAOI-3」幸运草 - 洛谷

破题思路

  • 我们观察到这里如果我们不操作，答案即为数组之和 sum

  • 操作一次之后的答案会发生变化

    • 选择 $[l, r]$, 把 $a_{l…r}全变成$ x，变后序列的和变为：

      $$
      sum−(a_l+a_{l+1}+…+a_r)+(r−l+1)×x
      $$

    • 那么 这次操作使得总和增加的量 为：
      $$
      inc =(r−l+1)×x−(a_l+…+a_r)
      $$

    • 我们要找 哪个区间 $[l, r]$ 的 inc 最大。

因此，答案 为：

  • $$
    max(sum, sum+max(inc))
    $$

转化问题

nc 就是想找到一个区间 $[l, r]，使得(r-l+1)\times x - (a_l + … + a_r)$ 最大。

把 $a_i 都替换为(x-a_i)$，就是“最大子段和”问题！（即 Kadane 算法）

  • 求 b i = x − a i 的最大连续子段和 ma x_in**c
  • 答案是：$\max(\text{sum}, \text{sum} + max_{inc})$

（因为可以不操作，或者选某段操作）

代码

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    long long x;
    cin >> n >> x;
    vector<long long> a(n);
    long long sum = 0;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }

    // 枚举操作区间，等价于求 b_i = x - a[i] 的最大子段和
    long long max_inc = 0; // 最大inc, 初始0 (也可能不选)
    long long curr = 0;
    for(int i = 0; i < n; ++i) {
        long long b = x - a[i];
        curr = max(b, curr + b);
        max_inc = max(max_inc, curr);
    }

    cout << max(sum, sum + max_inc) << endl;
    return 0;
}