数据结构学习笔记(1)--算法的威力I

自从出国的计划流产之后，决定利用现在这段实习的时间，重温一遍计算机基础学科，也就是数据结构、计算机组成、操作系统、数据库、编译原理和计算机网络，就按照这个顺序来慢慢的走了。

之前已经把M.A. Weiss的那本 Data Structure and Algorithm Analysis in C 2nd Edition看过了一遍，作为一本数据结构的本科教材。在讲解的细致程度和深入程度上，它绝对达到了相当的高度。作为一本讨论计算机算法的书，它也是经典中的经典。所以这次温习数据结构，用的教材还是它，而那本CLRS则是当成一本COOKBOOK来使用了，看C的代码还是要比看Pseudocode要舒服不少的。

从摩尔定律提出到现在，30多年过去了，计算机的性能以几何的速度增长，如果按照这个速度下去，没准有一天算法会丧失它的意义呢，呵呵。不过估计那一天还早呢，毕竟，有快的算法为什么还要用慢的呢，如果说解决同一个问题，一个方法要用不到一秒，另一个方法得耗个十年八年的，你会选择哪个方法呢？

这本书的开篇就提到了一些经典的问题例如最大数选择问题和最大子序列求和，这两个问题也是不少IT公司的常见笔试问题，解决方法有不少，不过真正的最优解法（线性时间内解决）就只有那一种。虽然这本书是1997年就有，2002年就有中文版了，但到现在还是没几个人知道它的解法，不得不感叹下如今国内IT人士基础的匮乏。

现在就拿这个最大子序列求和问题开始我的数据结构复习之路吧，呵呵。

问题很简单，就是给出N个整数，正的负的都有（正的是一定有的），求出其中连续的子序列的最大值。

例如：8,9,-10,12的结果是19；9,-10,3,2,-1,7,-6的结果就是11

一般人想到的解法是逐层遍历，也就是说把这N个整数所有的连续子序列的和都计算出来，然后取最大的那个，就是答案了，这样的程序并不难写：

实现的C#代码如下：

public static int ExhaustiveMaxSubsequenceSum(int[] arrNumbers)
{
int tempSum;
int maxSum = 0;
int count = arrNumbers.Length;
for (int i = 0; i < j =" i;" tempsum =" 0;" k =" i;">maxSum)
{
maxSum = tempSum;
}
}
}
return maxSum;
}

N个数的子序列有1*2/2+2*3/2+…+N*(N+1)/2种，也就是(N3+3N2+2N)/6中，复杂度为N3

然而仔细研究代码之后，发现最内层和次内层的循环存在冗余，可以合并，改良后的代码如下：

public static int ImprovedExhaustiveMaxSubsequenceSum(int[] arrNumbers)
{
int tempSum;
int maxSum = 0;
int count = arrNumbers.Length;
for (int i = 0; i < tempsum =" 0;" j =" i;">maxSum)
{
maxSum = tempSum;
}
}
}
return maxSum;
}

此时使用了两层循环，算法的复杂度为N2

还有没有解决的方法呢？是时候使用下递归了。