目录
2.6.3最大连续子序列和(最大子数组和)问题
2.6.3.1问题
2.6.3.2确定动态规则(DP、状态转移方程)、初始值
(1)直接相关状态
(2)当前状态值的确定
(3)动态规则(DP、状态转移方程)
(4)初始值
2.6.3.3动态规划算法代码实现
(1)完整代码
(2)程序速度优化
(3)最大和连续子序列(最大和子数组)
(4)最大和连续子序列的个数(数量)
最大连续子序列和(maximum continuous subsequence sum，MCSS)，给定序列A，求A中按顺序连续的元素构成的子序列的最大和，这个子序列称为序列A的最大和连续子序列，也称最大和子数组。本问题也称求最大子数组和，或最大连续子数列和，或最大子段和。
计算机的序列是指序列的元素在代码中呈现出的顺序与内存存储顺序一致，在计算机中序列是可以通过索引来引用的。在python中字符串、列表、元组都是序列。
子序列是保持原序列中的顺序，比如：’ea’是’eahjkf’的子序列，但’ae’不是它的子序列。本题是关于最大连续子序列和问题，这种序列一般是数字型的序列。比如：序列[3, 2, -7, 8,1, 4]，索引2位置的最大连续子序列和为-2，对应的连续子序列为[3, 2, -7]，而[3,-7]是不连续的，在原序列中有间隔，且其和为-4，在索引2位置不是最大的。显然，原序列本身也可以看作是自身的子序列，可以看着是特殊的子序列。
子序列可以是连续的和不连续的，这里的连续是指子序列中的元素在原序列中是不间隔、不间断的，也即在原序列中也是相邻（紧邻）的，这里的连续类似连贯的意思。
下面不仅求最大连续子序列和(最大子数组和、最大子段和)，还求出最大和连续子序列及其个数(数量)。
(1)直接相关状态
本题是在一个序列中找出最大连续子序列和(最大子数组和，maximum subarray sum)，要求子序列是连续的，且子序列的和最大。而我们前面求的是子序列的长度问题，也即子序列的元素个数问题。本题涉及到求和，因而在计算时会使用元素值，考虑到连续子序列，也就是对相邻元素值的累计并判断累计值在当前状态位置是否最大。这个相邻元素值的累计就是连续元素求和，要保证这种连续元素，当前状态i只能与前面状态i-1有关，与前面其他状态都会存在间隔的元素，也就是讲前面其他状态对应序列与当前状态i位置的元素构成的子序列存在间隔，它们之间在原序列中至少间隔有A[i-1]。
因此，要保持连续，当前状态值受能确保连续性特点的状态的影响，显然当前状态i的直接相关状态也只能是状态i-1，与其他状态都存在间隔，因为状态与序列A的元素位置是对应的。当前状态i的直接相关状态只能是状态i-1，由于本题是连续子序列求和问题，不需要像前面最长连续递增子序列问题那样进行状态之间条件判断限定。
(2)当前状态值的确定
状态与状态值是不能等同的，状态是一种定性的描述，状态值是问题所要求的一种定量的衡量。并不一定是所有的直接相关状态都参与确定当前状态值。当前状态值的唯一性确定还可能与状态转移的因素的作用、求解问题的要求、问题自身的规律特点有关。
由上面直接相关状态的分析可知，当前状态i的直接相关状态只能是i-1状态。
我们记状态i的值dp[i]为序列A的索引i位置的最大连续子序列和(最大子数组和)，由于当前状态i的直接相关状态只能是i-1状态，显然有dp[i]= dp[i-1]+A[i]，但我们是找当前状态i的最大连续子序列和，由于子序列是数列特点，数列是可以有正数和负数，因而，当前状态位置的元素与相邻元素构成的连续子序列，其和不一定比当前状态位置的元素大，比如：序列[3, 2, -7, 8,1, 4]，在索引3位置，8与前面元素构成的最大和连续子序列为[3, 2, -7, 8]，其和为6，显然6<8，因此，为获得当前状态i的最大连续子序列和，我们还