问题：输入一个数组，数组中一个或多个联系的数组成子数组，求所有子数组的和的最大值。

原理：

解决该问题有两个思路：
（1）扫描累加
（2）动态规划

思路一

以[1, -2, 3, 10, -4, 7, 2, -5]为例。初始化和r为0，扫描数组，加上1后r为1，加上-2后r为-1，加上3后，r为2，r比3本身还要小，因此可以抛弃3先前的和。r的累加从3开始。继续遍历数组，在遍历到-4前，r的值为13。r加上-4后比原理的13要小，但不为0，因此不能舍弃，因为它可能是一个潜在的结果，我们使用一个临时变量保存它。接下来继续往下遍历求和，比较新的和值和临时保存的和值，把较大的保存下来，以此下去，最后得到的临时变量为子数组最大和。

1
2
3
4
5
6
7
8
9
10
11
12
13
def find_greate_sum_of_subarray(array):
   if not array:
       return None
   subarray_sum = 0
   greate_subarray_sum = 0
   for i in range(len(array)):
       if subarray_sum <= 0:
           subarray_sum = array[i]
       else:
           subarray_sum += array[i]
       if subarray_sum > greate_subarray_sum:
           greate_subarray_sum = subarray_sum
   return greate_subarray_sum

如果需要返回最后一个满足和最大的子数组，函数修改如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_subarray_of_greate_sum(array):
    if not array:
        return None
    i = j = 0
    subarray_sum = 0
    greate_subarray_sum = 0
    for p in range(len(array)):
        if subarray_sum <= 0:
            subarray_sum = array[p]
            i = p
        else:
            subarray_sum += array[p]
        if subarray_sum > greate_subarray_sum:
            greate_subarray_sum = subarray_sum
            j = p
    return array[i:j+1], greate_subarray_sum

思路二

使用动态规划思想来分析该问题。如果使用s(i)来表示第i个数字结尾的子数组的最大和，那么s(i)的递推公式如下：

1
2
s(i) = array[i]; i=0 of s(i-1)<=0
s(i) = s(i-1) + array[i]; i!=0 and f(i-1)>0

理解该递推思路可以借助思路一，可以说，该递推过程只不过是思路一的数学表达。

根据递推过程不难实现函数。虽然直观上使用递归实现，但不难改为迭代方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
def find_create_sum_of_subarray_dynamicly(array):
    if not array:
        return 
    subarray_sum = 0
    greate_subarray_sum = 0
    for i in range(len(array)):
        if i == 0 or subarray_sum <= 0:
            subarray_sum = array[i]
        elif subarray_sum > 0:
            subarray_sum += array[i]
        if subarray_sum > greate_subarray_sum:
            greate_subarray_sum = subarray_sum
    return greate_subarray_sum

对比不难发现，它们的实现是一样的。原因是该动态规划表达式只不过是思路一的抽象数学表达。