蓝桥杯JAVA-14.连续最大子数组模板

个人博客 www.tothefor.com 蓝桥杯复习知识点汇总
目录
分为连续子数组和非连续子数组，在一维的情况下可以等同于字串和子序列的最大和。
连续子数组
对于一个数A[ i ]，若是A[ i ] 的左边累计数非负，那么加上A[ i ] 能使得值不小于A[ i ]，认为累计值对整体和是有贡献的。如果前几项累计值负数，则认为有害于总和。
一维
动态规划：算法时间复杂度：O(n)
对于一个数A[ i ]，若是A[ i ] 的左边累计数非负，那么加上A[ i ] 能使得值不小于A[ i ]，认为累计值对整体和是有贡献的。如果前几项累计值负数，则认为有害于总和，应丢弃。
dp[ i ]表示以a[ i ]结尾的「连续子数组的最大和」，不是整个数组的最大子数组和。

即：dp[ i ] = max{dp[ i-1 ] + a[ i ]，a[ i ] }；
初始状态：dp[0] = a[0];
i

蓝桥杯JAVA-14.连续最大子数组模板最先出现在Python成神之路。