1.4　算法优化

本节通过一个实例详细介绍算法优化的过程。

例1-3　最大连续子序列和的问题：给定（可能是负的）整数序列{A₁,A₂,…,A_N}，寻找（并标识）使的值最大的连续子序列。如果所有整数都是负的，那么最大连续子序列的和是0。

例如，假设输入是{−1,12,−5,13,−6,3}，则最大连续子序列的和是20，最大连续子序列包含第2项到第4项（如粗体字部分所示）。又如，对于输入{1,−3,4,−2,−1,6}，则最大连续子序列的和是7，最大连续子序列包含最后4项（如粗体字部分所示）。

选用最大连续子序列和的问题作为本节实例，是因为有很多种算法可以解决这个问题，而且这些算法的时间复杂度相差很大。本节将讨论4个算法。第一个算法是时间复杂度为O(n3)的算法，采用枚举法，效率很低。第二个算法是时间复杂度为O(n2)的算法，它对第一个算法做了改进。第三个算法是时间复杂度为O(n log n)的算法，它采用分治法。最后一个算法是时间复杂度为O(n)的算法，效率很高，但不易想到，也不易理解。