基础算法记录——由最大子序列和想到的

这是一个入门级的算法，但它却揭示了计算机算法设计的一些核心思想：枚举与分治递归。

这篇文章主要由简单到复杂来解析这一问题，流程大致是：枚举求解（充分利用计算机的计算能力来解决单调复杂问题），算法分析与改进（相对偏移化简枚举法），分治算法（divide-conquer，计算机核心思想之一），递归算法与递归的使用原则，最后依然使用算法分析的技术来改进上面的算法。

1）枚举法，这应该是计算机从业人员最熟悉，最简单的算法。想想你以前写过的那些程序，现在回头再看时，估计自己都会被恶心到。但是当你再过几年code&debug后，我觉得很多人都会对它心生敬畏。枚举法是人类面对浩瀚宇宙，繁杂事物所能做出的最本能和卑微的抵抗。想想你所认知的世界，对知识经验的积累传承，无时无刻都在使用枚举法。

所以，从某种意义上说程序员遇到问题，使用枚举法——这是全人类的本能，无可厚非，甚至应该有所提倡。可惜的是很多人到此为止，不愿意对它刨根问底，改进优化。我想这应该是程序员优秀与否的一个重要标志。

下面来看看这个问题，一个整数序列v[0],...,v[N],找到一个连续的和最大的子序列v[m],..v[m+n].

最简单的方法（应该是最本质的方法）是，我把这个整数序列中所有的子序列都一一列出来，计算每个子序列的和，比较保留最大的那个子序列就可以了。

是的，就应该这么想：下面的问题就是如何实现子序列的选取和求和，这里就有个核心要抓住『连续』。连续就意味着你可以用数组的索引和指针去选取一个个子序列，比较最近两个和，保留最大的那个。

int  maxSum1(vector<int> &v, int & nFrom, int &nTo)

{

    int nsum =0;

    if(v.size() > 0)

    {

　　　　for(int i =0; i<v.size(); i++)

　　　　{

　　　　　　int vsum =0;

　　　　　　for(int j=i; j<v.size(); j++)

　　　　　　{

　　　　　　　　for(int k =i; k<=j; k++)

　　　　　　　　　　vsum+=v[k];

　　　　　　　　if(nsum< vsum)

　　　　　　　　{    nFrom = i, nTo = j;

　　　　　　　　　　nsum = vsum;}

　　　　　　}

　　　　}

　 }

　else

　　　　return 0;

return nsum;

}

下面来进一步的分析一下上面的枚举法的时间复杂度，很简单3个for循环，T（N）=O(N^3)。这里多说几句，一般我们第一次写出来的程序，如果是这个复杂度，那请注意了，这种情况往往有经验可以肯定:这不是最优解。一般可以降到O(N^2),甚至是O(NlogN)。下面就是由里到外的降loop复杂度，这里有个标志就是最里面的循环变量是依赖与外层的循环变量。于是：

int  maxSum1(vector<int> &v, int & nFrom, int &nTo)

{

    int nsum =0;

    if(v.size() > 0)

    {

　　　　for(int i =0; i<v.size(); i++)

　　　　{　　int vsum =0;

　　　　　　for(int j=i; j<v.size(); j++)

　　　　　　{

　　　　　　　　vsum+=v[j];

　　　　　　　　if(nsum< vsum)

　　　　　　　　{    nFrom = i, nTo = j;

　　　　　　　　　　nsum = vsum;}

　　　　　　}

　　　　}

　 }

　else

　　　　return 0;

return nsum;

}

这时候我们通过扩大计算连续和的范围由原来k:i~j,变到了i~v.size();问题来了，这是否意味着T（N）=O（N^2）是算法的最优解呢。同样要抛弃学院派的理论论证，我们先换个思路来思考：众所周知，O(N^3)>O(N^2)>O(NlogN)>O(N)，于是我们猥琐的把目标指向了O(NlogN).一旦看到它，你是否有了点骚动了呢？

2）对！二分法的时间复杂度就是这个！于是我又无耻的想到了是否可以用二分法来将问题一分为二地单独处理其中一个。。。

注意这个时候，我们需要认真分析一下二分法思想（分治算法）：问题可以不断的一分为二处理，直到基准情况（此状态必须是已知的）。最后只需要将2种情况合二为一即可得到最优解。

int popMax3(int n1, int n2, int n3)

{

　　if(n1>n2)

　　　　if(n1>n3)

　　　　　　return n1;

　　　　else

　　　　　　return n3;

　　else{

　　　　　　if(n2 > n3)

　　　　　　　　return n2;

　　　　　　else

　　　　　　　　return n3;

　　　　}

}

int  getMaxSubSum(std::vector<int> &v, int &nL, int &nR)

{

　　if(nR == nL)

　　　　if(v[nL]>0)

　　　　return  v[nL];

　　else

　　　　return 0;

//////////////////////////Divide////////////////////////////////

     int nCenter = (nR+nL)/2;

　  int nLsum = getMaxSubSum(v, nL, nCenter);//max sum is left of center

     int nRsum= getMaxSubSum(v, nCenter, nR);//max sum is right of center

//max sum is at left and right of center

      int nHLsum =0, nHRsum = 0 , vsum =0;

　　for(int i = nCenter; i >= nL; i--)

　　{

　　　　vsum +=v[i];

　　　　if(nHLsum < vsum)

　　　　　　nHLsum = vsum;

　　}

     vsum =0;

　　for(int j = nCenter+1; j <= nR; j++)

　　{

　　　　vsum +=v[j];

　　　　if(nHRsum < vsum)

　　　　　　nHRsum = vsum;

　　}

///////////////////////Conquer////////////////////////////

return  popMax3(nLsum, nRsum, nHLsum+nHRsum);

}

上面就是典型的Divide&Conquer算法的结构，下面需要对其进行时间复杂度分析，很简单：T(N) = T(L)+T(R)+N/2+N/2;于是可以得到：T(N)=2T(N/2)+N;

接下来，数学帝们估计就开始显摆了，其实你再仔细看看，或者干脆把T换成S，明白了吧——这是高中数学的问题了。设N = 2^k,k表示我们需要将一个问题divide几次才能分到基准情况（即nR==nL）,于是T(N)= NlogN+N = O(NlogN);写到这里，我想很多人觉得这个问题结束了，或者还有一部分人觉得还有O(N)的解法，但是，我要在这个时候引出另一个问题，上面的算法你觉得最核心的是什么？分治，是其一吧。还有呢？

3）递归

是的，递归。那么问题来了？一堆屌丝大叫到，为嘛用『递归』？难道只要可以分解为类似求解方式的问题（比如2分问题，比如斐波那契问题），都可以用递归吗？

如果是，递归不是要逆天吗？（这一句，大神当我没说！）

下面来一一回答：

首先要负责任的解释一下所谓的递归：递进归纳。一个大的问题可以归纳为一些较小的问题，而较小问题的解是可以假设验证是正确的，当反向追溯问题的解释，其实就是在递进寻找问题的本源。如果你学过卷积算法，认为卷积是系统响应的积累结果，那递归则是，你拿着这个积累结果，按照一个规范（可以理解为一个数学公式）去追溯引起积累结果的本源（类似激起涟漪的石块）。

也许你糊涂了，不过没关系，你要的是如何正确使用？很简单，如果一个问题按照一个规则（不管它多么复杂，例如汉诺塔问题，8皇后问题等等。。。）不断演进，只要你知道它最原始的情况或状态，你就可以大胆的使用『递归』。

但是请不要得意忘形，因为递归也有个使用指南。这个指南的伟大意义在于它直接关系到程序设计的成功与否：

递归四原则：

1.基准情形，要已知。

2.推进方向，向基准。

3.每层递归，可运行。

4.合成效益，要独立，少交叉。

这里只解释一下第三，四2点，其实这就一个核心意思：递归的每层要一致，不能有多种情况。当递归每层时，每个递归层最好不要有交叉。这样会让算法大量的进行重复计算，对时空消耗都是不明智的做法。就好像你计算输入为N的情况，就要递归求N-1和N-2的情况，但是计算N-1的递归时，你又要计算一次N-2的情况。具体的分析和时间复杂度可能都没变化，但是实际随着N的增加，算法的时空消耗往往波动较大。比如斐波那契递归实现，就有这种问题。

OK，这算是说完了该说的重点。下面再继续缩减这个算法的时间复杂度的问题，下文再补上。。。