蓝桥杯算法提高VIP-和最大子序列 （C语言代码）

解题思路:

之前写过这个题解，大家可以看看最佳题解。

下面介绍动态规划的做法，复杂度为 O(n)。

　　步骤 1：令状态 dp[i] 表示以 A[i] 作为末尾的连续序列的最大和（这里是说 A[i] 必须作为连续序列的末尾）。

　　步骤 2：做如下考虑：因为 dp[i] 要求是必须以 A[i] 结尾的连续序列，那么只有两种情况：

 这个最大和的连续序列只有一个元素，即以 A[i] 开始，以 A[i] 结尾。

 这个最大和的连续序列有多个元素，即从前面某处 A[p] 开始 (p<i)，一直到 A[i] 结尾。

　　对第一种情况，最大和就是 A[i] 本身。

　　对第二种情况，最大和是 dp[i-1]+A[i]。

　　于是得到状态转移方程：

　　　　　　　　dp[i] = max{A[i], dp[i-1]+A[i]}

　　这个式子只和 i 与 i 之前的元素有关，且边界为 dp[0] = A[0]，由此从小到大枚举 i，即可得到整个 dp 数组。接着输出 dp[0]，dp[1]，...，dp[n-1] 中的最大子即为最大连续子序列的和。

注意事项:

参考代码:

代码后面补上  因为机房这电脑在网站上不能调整代码格式， 晚上回去用自己电脑