另一方面，主题给出k个整数序列{ N1，N2，…，NK }，其任意连续子序列可表示为{ Ni，Ni 1，…，Nj }，其中1=i=j=K。 大连连续子串是所有连续子串中元素和最大的一个，例如，给定子串{-2、11、- 4、13、-5、-2 }，大连连续子串为{ 11、- 4、-2 }，最大和20。
二、解题思路动态规划解题思路详见另一篇文章。
为了简化状态的定义，可以定义dp[i]，表示以a[i]为末尾的连续序列之和。 其中数组a[]表示整数序列。 因此，我们求出的连续子串的要素和最大数量是数组dp的最大数量。
定义状态转移方程，知道动态规划满足无后向性。 也就是说，各阶段的决策只受到以前决策的影响，但不影响之后各阶段的决策。 于是，可以从后向前推出状态转移方程。 考虑到dp[i]和dp[i-1]的关系，假设连续数组中的元素保存在数组a[]中，是否一定为dp[i]=dp[i-1] a[i]？ 答案不一定。 假设只有在dp[i-1] a[i] a[i]的情况下，dp[i]=dp[i-1] a[i]的等式才可能成立。 否则，dp[i]可以从a[i]开始重新计数。 这样，就得到了状态转移方程。
DP[I]=max(DP[I-1]a[i]，a[I] )。
从公式中可以看出，为什么dp[i]表示以a[i]为末尾的连续序列的和。
确定边界由状态定义，当i=0时，dp[0]=0；
三、代码编写# include stdio.h # include stdlib.h # definen7# definemax (a，b ) ) ab？ a:b ) int main () { int a[N]={0，- 2，11，- 4，13，-5，-2}； //存储最大连续子序列和int maxResult=0的//dp[i]是以a[i]为末尾的连续序列的和int dp[N]={0}； //核心算法int i=1； for(I； i N； I ) ) DP[I]=max((DP[I-1]a[i] )，a[I] )； if(maxresultDP[I] ) maxresult=DP[I]； } } printf ('最大连续子序列之和：%d '，maxResult )； 返回0； (四、运行结果
五、总结动态规划必须满足无后向性，可以逆向思维推出状态转换方程。 关于动态计划的求解方法，请参照另一篇文章。