下载掌阅APP，畅读海量书库
立即打开
本节通过一个实例详细介绍算法优化的过程。
例1-3 最大连续子序列和的问题：给定（可能是负的）整数序列{
A
1
,
A
2
,…,
A
N
}，寻找（并标识）使
的值最大的连续子序列。如果所有整数都是负的，那么最大连续子序列的和是0。
例如，假设输入是{−1,12,−5,13,−6,3}，则最大连续子序列的和是20，最大连续子序列包含第2项到第4项（如粗体字部分所示）。又如，对于输入{1,−3,4,−2,−1,6}，则最大连续子序列的和是7，最大连续子序列包含最后4项（如粗体字部分所示）。
选用最大连续子序列和的问题作为本节实例，是因为有很多种算法可以解决这个问题，而且这些算法的时间复杂度相差很大。本节将讨论4个算法。第一个算法是时间复杂度为 O ( n 3 )的算法，采用枚举法，效率很低。第二个算法是时间复杂度为 O ( n 2 )的算法，它对第一个算法做了改进。第三个算法是时间复杂度为 O ( n log n )的算法，它采用分治法。最后一个算法是时间复杂度为 O ( n )的算法，效率很高，但不易想到，也不易理解。