Algorithm - Problem - 最大子段和

给出一段序列 aa,选出其中连续且非空的一段使这段和最大,求这个最大的和.

分治

分析

分治的递归边界为单个元素,此时直接返回该元素的值.
对于数组 aa[l,r][l, r] 区间,其最大子段和的函数调用记为 SUB(l,r)\mathrm{SUB}(l, r).
递归调用时,m(l+r)/2m\leftarrow (l+r)/2,其最大子段和有三种情况

  1. 最大子段和出现在 [l,m][l, m] 区间.
  2. 最大子段和出现再 [m+1,r][m + 1, r] 区间.
  3. 最大子段和跨越了 mm.

我们可以分别计算三种情况,并取最大值返回,以下是三种情况的计算方法

  1. 递归调用 SUB(l,m)\mathrm{SUB}(l, m).
  2. 递归调用 SUB(m+1,r)\mathrm{SUB}(m + 1, r).
  3. 求左区间以 a[m]a[m] 为尾的最大子段和 s1s_1 以及右区间以 a[m+1]a[m + 1] 为首的最大子段和 s2s_2,则此时的值为 s1+s2s_1+s_2.

于是 [l,r][l, r] 区间上的最大子段和为 max{SUB(l,m),SUB(m+1,r),s1+s2}\max\{\mathrm{SUB}(l, m), \mathrm{SUB}(m + 1, r), s_1+s_2\}.

复杂度分析

T(n)=2T(2n)+O(n)T(n) = 2T(\frac{2}{n}) + \mathcal{O}(n),时间复杂度为 O(nlogn)\mathcal{O}(n\log n)

代码

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
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MAXN (200000+5)
int divmaxsub(int *a, int l, int r)
{
if(l == r) return a[l];
int s;
int m = (l + r) / 2;
int lv = divmaxsub(a, l, m);
int rv = divmaxsub(a, m + 1, r);
int s1 = -2147483648U, s2 = -2147483648U;
int ts1 = 0, ts2 = 0;
for(int li = m; li >= l; li--)
{
ts1 += a[li];
if(ts1 > s1) s1 = ts1;
}
for(int ri = m + 1; ri <= r; ri++)
{
ts2 += a[ri];
if(ts2 > s2) s2 = ts2;
}
s = s1 + s2;
s = MAX(lv, s);
s = MAX(rv, s);
return s;
}

动态规划

分析

最大子段和 XX 实际上是求

X=max{k=ija[k]i,j:0ijn1}.X=\max\left\{\sum_{k=i}^{j}a[k]\Bigg|\forall i,j:0\leqslant i\leqslant j\leqslant n-1\right\}.

为方便起见,此处假定下标从 11 开始,以 nn 结束,转为

X=max{k=ija[k]i,j:1ijn}.X=\max\left\{\sum_{k=i}^{j}a[k]\Bigg|\forall i,j:1\leqslant i\leqslant j\leqslant n\right\}.

此处有两个变量 iijj 变化,我们可以根据 max\max 的性质作出一些变化.
假设有 a,b,c,d,e,fa, b, c, d, e, f 六个变量,显然 max{a,b,c,d,e,f}=max{max{a,c},max{b,d},max{e,f}}\max\left\{a,b,c,d,e,f\right\} = \max\left\{\max\left\{a, c\right\}, \max\left\{b, d\right\}, \max\left\{e, f\right\}\right\}.
也就是说,我们可以对要求的值进行分组,分别求每个组内的最大值后,再求所有组的最大值.
我们不妨将所有上标 jj 相同的值,分为一组,则转化为

X=max{max{k=ija[k]j=1,i:1ij},,max{k=ija[k]j=n,i:1ij}}.X=\max\left\{\max\left\{\sum_{k=i}^{j}a[k]\Bigg|j = 1, \forall i : 1\leqslant i\leqslant j\right\}, \cdots, \max\left\{\sum_{k=i}^{j}a[k]\Bigg|j = n, \forall i : 1\leqslant i\leqslant j\right\}\right\}.

我们不妨令

b[j]=max{k=ija[k]i:1ij}b[j] = \max\left\{\sum_{k=i}^{j}a[k]\Bigg|\forall i : 1\leqslant i\leqslant j\right\}

则有

X=max{b[1],b[2],,b[n]}=max{b[j]j:1jn}X = \max\left\{b[1], b[2], \cdots, b[n]\right\} = \max\left\{b[j]\big|\forall j : 1\leqslant j \leqslant n\right\}

观察 b[j]b[j],其代表的实际上是以 a[j]a[j] 为尾的最大子段和,而求 b[j]b[j] 我们有两种决策

  1. b[j]=b[j1]+a[j]b[j] = b[j - 1] + a[j].
  2. b[j]=a[j]b[j] = a[j].

因此我们有递推式

b[j]=max{b[j1]+a[j],a[j]}.b[j] = \max\left\{b[j-1]+a[j], a[j]\right\}.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MAXN (200000+5)
int dp(int *a, int n)
{
int b[MAXN];
int s = a[0];
b[0] = a[0];
for(int i = 1; i < n; i++)
{
b[i] = MAX(b[i - 1] + a[i], a[i]);
if(b[i] > s) s = b[i];
}
return s;
}