最大子串和算法与归纳递推法

作者: 天之見證 | 来源:发表于2020-03-17 00:27 被阅读0次

1. 问题描述

现有一个整数序列 ( $2,-3,1,5,-1,3,-2,-3,3, \ldots$ ), 长度为 $n$ , 求具有最大和的子串

2. 初次的归纳递推尝试

现有序列 $S=(x_1,x_2,\ldots,x_n)$

假设:

已知长度小于 $n$ 的序列所对应的最大子串和

即: 我们现在知道对于序列 $S'=(x_1,x_2,\ldots,x_{n-1})$ 对应的最大子串和, 可假设为 $S'_M=(x_i,x_{i+1},\ldots,x_j), 1\le i\le j\le {n-1}$

分条件讨论如下:

$j$	$x_n$	$S'_M$
$j=n-1$	$x_n>0$	$(S'_m,x_n)$
$j=n-1$	$x_n<=0$	$S'_M$
$j<n-1$		1. $S'_M$ 保持不变 2. 加上 $x_n$ 之后, 原来不是最大的变成最大的了(此时得到的串一定是以 $x_n$ 结尾的)

可见, 在第三种情况的时候, 并不能得出明确的结论

3. 更强的假设

假设:

已知长度小于 $n$ 的序列所对应的最大子串和和以 $x_{n-1}$ 结尾的最大的子串 $S'_{suffix}$

接着上表的第3种情况分析:

情况	$S'_M$	备注
$sum(S'_{suffix})+x_n \le sum(S'_M)$	$S'_M$	其中的第1点可以明确了
$sum(S'_{suffix})+x_n > sum(S'_M)$	$(S'_{suffix},x_n)$	其中的第2点可以明确了

这里不再需要考虑 $x_n$ 是否大于0了

4. 伪代码

global_max = 0
suffix_max = 0
for i in range(0, len(arr)):
  if arr[i] + suffix_max > global_max:
    suffix_max = suffix_max + arr[i]
    global_max = suffix_max
  elif arr[i] + suffix_max > 0:
    suffix_max = suffix_max + arr[i]  // 这里可以维持住suffix的最大这种情况
  else: // arr[i] < 0 且很小
    suffix_max = 0

5. 加强型归纳递推

一般的归纳递推:

$P(\lt n) \Rightarrow P(n)$

加强型归纳递推:

$[P \& Q](\lt n) \Rightarrow P(n)$

在加强型的情况下其实隐含了 $[P \& Q](\lt n) \Rightarrow [P \& Q](n)$

引入了 $Q$ 的代价就是你得维护这个 $Q$ 的状态迁移, 即 $Q(n-1) \Rightarrow Q(n)$ , 这个也必须是可证明或者是确定的

就如上面代码中的 suffix_max 这个变量的维护

ref:

Introduction to algorithm a creative approach [udi manber]
https://mathoverflow.net/questions/31699/strengthening-the-induction-hypothesis

网友评论

本文标题：最大子串和算法与归纳递推法

本文链接：https://www.haomeiwen.com/subject/cfvaehtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！