最大连续和，也称最大连续子段和。这个问题虽然简单，但其中蕴含了很多算法的思想，包括动态规划和分治法。
问题描述
最大连续和问题 给出一个长度为n的序列A0,A1,...,An-1，求最大连续和。也就是，要求找到一组(i,j)满足0≤i≤j≤n-1，使得Ai+Ai+1+...+Aj尽量大。
解法1 暴力枚举
我们可以枚举出所有的连续和，记B(i,j)=Ai+Ai+1+...+Aj，也就是 i 从0取到n-1，j 从 i 取到n-1。因此，我们要做的分为两部分，第一部分是枚举出所有的B(i,j)，第二部分是对于具体的B(i,j)计算它的值，计算B(i,j)的值的时间花费为j-i+1，因此总的时间复杂度为
网友评论
