算法分析之最大子串和
介绍
本文介绍最大子串和问题的解决 主要包括两种基础版 和 取模版 提供经典解法和详细分析。 
STL:帮助文档
最大子串和
定义
一、 最大子段和问题 (Maximum Subarray Sum)1. 定义给定一个长度为
n
n
n 的数组
a
[
1
…
n
]
a[1 \\dots n]
a[1…n]，求其所有连续子段和的最大值。数学表达为：
max
1
≤
l
≤
r
≤
n
∑
i
=
l
r
a
i
\\max_{1 \\le l \\le r \\le n} \\sum_{i=l}^{r} a_i
1≤l≤r≤nmaxi=l∑rai
核心基础
二、 核心基础：前缀和 (Prefix Sum)1. 定义前缀和
p
r
e
f
i
x
[
i
]
prefix[i]
prefix[i] 表示从数组第
1
1
1 个元素到第
i
i
i 个元素的累加和：
p
r
e
f
i
x
[
i
]
=
∑
k
=
1
i
a
k
prefix[i] = \\sum_{k=1}^{i} a_k
prefix[i]=k=1∑iak2. 核心转化利用前缀和，我们可以将任意区间和的计算简化为两个点的操作：
s
u
m
(
l
,
r
)
=
p
r
e
f
i
x
[
r
]
−
p
r
e
f
i
x
[
l
−
1
]
sum(l, r) = prefix[r] – prefix[l-1]
sum(l,r)=prefix[r]−prefix[l−1]核心思想：这一步实现了 区间问题
→
\\rightarrow
→ 两点差值 的转化。这是解决所有子段、区间问题的基石。
Question1
题目OJ
method1
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int prefix,min_prefix;
prefix = min_prefix = 0;
int ans = –1e5;
for(int i = 0;i<nums.size();i++){
prefix += nums[i];
ans = max(ans,prefix–min_prefix);
min_prefix = min(prefix,min_prefix);
}
return ans;
}
};
analysis
经典prefix前缀和解法： sum(l,r) = prefix[R] – prefix[L-1] 求取ans 最大时 就是要prefix[R] – prefix[L-1](这个最小时 ans 最大) 即我们要找到min_prefix（历史最小值） 求取ans的时候 要实时更新 要取max**
error
前缀和prefix 都是 0 ans 要找最小值的或者nums[0] 不能是0 因为nums[i] 里面可能都是负数
method2
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum,ans;
sum = 0;
ans = –1e5;
for(int i = 0;i<nums.size();i++){
sum = max(nums[i],nums[i]+sum);
ans = max(sum,ans);
}
return ans;
}
};
analysis
kadane算法: 如果前面的和是负的，就不要它，从当前位置重新开始。即是动态规划 同时需要ans 记录 历史最大值
error
同上
Question2
核心推导
核心逻辑推导我们要最大化区间和取模的结果：
max
{
(
s
u
m
(
l
,
r
)
(
m
o
d
p
)
)
}
\\max \\{(sum(l, r) \\pmod p)\\}
max{(sum(l,r)(modp))}根据前缀和公式
s
u
m
(
l
,
r
)
=
p
r
e
f
i
x
[
r
]
−
p
r
e
f
i
x
[
l
]
sum(l, r) = prefix[r] – prefix[l]
sum(l,r)=prefix[r]−prefix[l]，在模
p
p
p 意义下，这个式子等价于：
(
p
r
e
f
i
x
[
r
]
−
p
r
e
f
i
x
[
l
]
+
p
)
(
m
o
d
p
)
(prefix[r] – prefix[l] + p) \\pmod p
(prefix[r]−prefix[l]+p)(modp)分情况讨论为了让上述结果尽可能大（即接近
p
−
1
p-1
p−1），我们需要根据
p
r
e
f
i
x
[
r
]
prefix[r]
prefix[r] 和
p
r
e
f
i
x
[
l
]
prefix[l]
prefix[l] 的大小关系分为两种情况：当
p
r
e
f
i
x
[
r
]
≥
p
r
e
f
i
x
[
l
]
prefix[r] \\ge prefix[l]
prefix[r]≥prefix[l] 时：结果为
p
r
e
f
i
x
[
r
]
−
p
r
e
f
i
x
[
l
]
prefix[r] – prefix[l]
prefix[r]−prefix[l]。要使结果最大，我们需要
p
r
e
f
i
x
[
l
]
prefix[l]
prefix[l] 越小越好（理想情况是
0
0
0）。当
p
r
e
f
i
x
[
r
]
<
p
r
e
f
i
x
[
l
]
prefix[r] < prefix[l]
prefix[r]<prefix[l] 时：结果为
p
r
e
f
i
x
[
r
]
−
p
r
e
f
i
x
[
l
]
+
p
prefix[r] – prefix[l] + p
prefix[r]−prefix[l]+p。
题目OJ
method
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long p;
cin >> n >> p;
vector<long long>vc(n);
for (int i = 0; i < n; i++) {
cin >> vc[i];
}
set<pair<long long, int>>s;
long long prefix = 0;
long long ans = 0;
int L = 0, R = 0;
s.insert({ 0,–1 });
for (int i = 0; i < n; i++) {
prefix = (prefix + vc[i]) % p;
if (prefix > ans) {
ans = prefix;
L = 0;
R = i;
}
auto it = s.upper_bound({prefix,1e9});
if (it != s.end()) {
long long val = (prefix – it->first + p) % p;
if (val > ans) {
ans = val;
L = it->second + 1;
R = i;
}
s.insert({ prefix,i });
}
}
cout<<L<<R<<ans<<endl;
}
analysis
1.计算当前前缀和：
c
u
r
r
=
(
c
u
r
r
+
a
[
i
]
)
(
m
o
d
p
)
curr = (curr + a[i]) \\pmod p
curr=(curr+a[i])(modp)。 2.查找最佳
p
r
e
f
i
x
[
l
]
prefix[l]
prefix[l]： 在集合中执行 s.upper_bound(curr)。更新最大值：如果找到了 it = s.upper_bound(curr)，则更新 ans = max(ans, (curr – *it + p) % p)。 3.如果没找到（说明
c
u
r
r
curr
curr 是目前最大的），则更新 ans = max(ans, curr)（即
p
r
e
f
i
x
[
l
]
=
0
prefix[l]=0
prefix[l]=0 的情况）。 4.存入集合： 将
c
u
r
r
curr
curr 插入 set。
关键结论: 由于情况 2 多加了一个
p
p
p，它通常比情况 1 更有可能产生更大的结果。要使
p
r
e
f
i
x
[
r
]
−
p
r
e
f
i
x
[
l
]
+
p
prefix[r] – prefix[l] + p
prefix[r]−prefix[l]+p 最大，我们需要：
p
r
e
f
i
x
[
l
]
>
p
r
e
f
i
x
[
r
]
prefix[l] > prefix[r]
prefix[l]>prefix[r] （保证进入情况 2）
p
r
e
f
i
x
[
l
]
prefix[l]
prefix[l] 尽可能小 （减去的项越小，差值越大）因此，对于每一个确定的
p
r
e
f
i
x
[
r
]
prefix[r]
prefix[r]，我们需要在已处理的前缀和集合中寻找：最小的、且大于
p
r
e
f
i
x
[
r
]
prefix[r]
prefix[r] 的值。
总结
下篇文章 我们将学习算法中的双指针算法。
