子序列求和最大问题

　　子序列求和最大问题是给定一个序列数组，求出连续序列的子数组的和最大。这样的问题可以用动态规划来求解，关于动态规划，在前面已经做了比较详细的讲解了。https://www.cnblogs.com/wancy/p/16741342.html

1. 子序列求和

　　假设现在有一个数组为[1,-2,0,3,-2,4,6,-5,2]，根据排列组合那么它的连续子序列有(n * (n + 1)) / 2个，非空子序列有2^n-1个。通过观察发现[3,-2,4,6]组成的连续序列和最大。但是如果采用程序实现，最容易考虑到使用穷举法，比如我们可以使用循环结构先找连续序列为1个、2个...、9个，就能找出所有的连续序列了，对这些连续序列求和，找出值最大的对应的连续序列就是我们要求得结果，时间复杂度容易求得为O(n^2)。很显然，复杂度较高，使用动态规划就可以在线性时间复杂度O(n)内实现这一目标。

2. 动态规划基本问题

　　上讲已经讲过，动态规划包含最优子结构、重叠子问题、备忘录方法三个问题。假设给定一个序列,比如：[1, -2, 0, 3, -2, 4, 6, -5, 2],我们可以这样想，如果第一个数是负数，是不是可以直接跳过，我们从第一个是正数的地方开始看，因为连续子序列的最前面肯定不能是负数的，最后面也不可能是负数，就比如，[负数，负数，正数，正数，负数，正数，负数]这个序列，我们知道去掉前面的负数与最后面的负数，子序列的和肯定变大了。在遍历一边序列的前提下，我们只需要备份前n个序列中（下标0~k）最大的子序列（最大子序列不一定下标能取到k）的和及子序列的起始与终止位置，这个通过比较加入下一个元素后，与没加入之前的之前的和最大的最优子序列。现在已经知道了前k个的最大和子序列与位置， 如果加入的一个元素为正数，很显然，最大子序列就应该把这个元素包括进去，并且最大和子序列的结尾位置的下标加1，如果是负数，那么先不着急，先把这个元素求和，也就是原先的最优子序列加上这个数，如果加上这个负数后，和为负数了，这个元素肯定不能要了，具体什么意思了？，比如下一个元素为-1000000000000000，你是不是想都不用想，这个数肯定不能加入进去，直接从这个位置的下一个位置开始再往后看子序列。如果加上这个负数后，和仍然为正数，比如你的子序列加入了一个-1，你是不是会想到往后面再看几个元素，如果后面又出现了较大的正数，比如999999，是不是这个-1也在这个最大和子序列中了，所以，当加入的数为负数时，且子序列仍然为正数时，我们先把这个下标先记录下来，继续向后遍历，直到子序列小于零或者比原来的的子序列和要大，比如[正，正，正，负，负，正，正，正]，我们是不是要[正，正，正，负，负]判断求和是不是大于0，还是小于0，如果大于零，是不是[正，正，正]的和要与[正，正，正，负，负，正，正，正]的和比较大小就可以了。然后再更新记录初始与结尾的下标就可以了，到此，估计没有人能听得懂我讲的吧。看下面的这个[1, -2, 0, 3, -2, 4, 6, -5, 2]例子吧。假设初始化最大和子序列为0，下标为0.

　　　　　　　　　　　　　　　　　　　　　　　　序列[1, -2, 0, 3, -2, 4, 6, -5, 2]

　　　　　　　　　　　　　　　　　　　　　　　　下标[0,  1, 2, 3,  4, 5, 6,  7,  8]

1.遍历元素，元素为1

　　元素1+初始化子序列的和0=1,1是大于初始和0的，说明子序列的和为1，起始下标为0，结尾下标为0.

2.遍历元素，元素为-2

　　元素-2+子序列的和1=-1，-1是小于0的，那么前两个子序列的目标结果就是子序列的和为1，起始下标为0，结尾下标为0。包含有-2的子序列的和我们记作0就可以了，标志作用，然后记录临时起始的新的位置下一个位置。

3.遍历元素，元素为0

　　上一轮包含有-2的子序列的和标志为0，此刻不需要计算-2了，子序列从此断开了，最优的结果一定是-2之前的子序列或者是-2之后的子序列了；

　　元素0的值为0，包含有0的子序列的和我们仍然记作0就可以了，临时下标继续往后滑动。自此，我们遍历完0后，知道了最优子序列为1，及其下标位置。

4.遍历元素，元素为3

　　元素3+包含有0的子序列的和0=3，3大于0，那么包含元素3的子序列的和为3，是大于之前记录的最长子序列的和1的。所以更新最大和子序列的和为3，起始于结尾位置3,3.至此，我们找到了前四个元素的最大和子序列为3.

5.遍历元素，元素为-2

　　元素-2+包含有3的序列和3=1,1是大于0的，但是小于记录的最优子序列的和3，此时记录包含有-2的最大子序列和为1（临时记录）

6.遍历元素，元素为4

　　元素4+包含有-2的最大子序列和1=5,5是大于最优和3的，那么更新最优的结尾位置为4的下标位置，初始位置还是元素3的位置不用动。此时，我们得到了最优子序列3,-2,4了，包含有4的最大和子序列也是3,-2,4，也知道了其起始与结尾的下标。

7.遍历元素，元素为6

　　元素6+包含有4的最大子序列和5=11,11是大于最优子序列和5的，所以更新最优子序列的和的值与下标的起始位置与结尾位置。此时，我们得到了最优子序列3, -2, 4, 6了，包含有6的最优（文中最优就是和最大）子序列也是这个。

8.遍历元素，元素为-5

　　元素-5+包含有6的最大子序列和11=6，6是大于0的，比最优和11小，此时，记录包含有-5的最大子序列和为6（临时记录）。

9.遍历元素，元素为2

　　元素2+包含有-5的最大子序列和6=8,8是大于0的，但是比最优和11小，此时记录包含有2的最大子序列和为8（临时记录）。遍历结束了，最优的结果出现在遍历元素，元素为6的地方，其结果为3, -2, 4, 6。

　　至此，一个循环遍历完了，计算得到了最大的子序列的和及其子序列。

　　以下是python代码实现：

from typing import Union

def max_subarray_with_indices(array) -> Union[int, float]:
    contained_element_subarray_max = 0
    subarray_max = 0
    start_index = 0
    end_index = 0
    temp_start_index = 0
    for i, element in enumerate(array):
        if contained_element_subarray_max + element > 0:
            contained_element_subarray_max = contained_element_subarray_max + element
        else:
            contained_element_subarray_max = 0
            temp_start_index = i + 1

        if contained_element_subarray_max > subarray_max:
            subarray_max = contained_element_subarray_max
            start_index = temp_start_index
            end_index = i

    # 找到最大子序列的起始和结束索引后，可以得到最大子序列
    max_subarray = array[start_index:end_index + 1]

    return subarray_max, max_subarray

if __name__ == '__main__':
    arr = [1, -2, 0, 3, -2, 4, 6, -5, 2]
    # arr = [1, 2, 0, 3, 2, 4, 6, 5, 2]
    max_sum, max_subarray = max_subarray_with_indices(arr)

    print("最大子序列和:", max_sum)#11
    print("最大子序列:", max_subarray)#[3, -2, 4, 6]

　　小结：可能本人讲述的还不是很清楚，自己按照代码推理一遍就明白了。 　　

　　若存在不足或错误之处，欢迎指正与讨论！