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

2020-03-17 本文已影响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