学步园

      问题描述：给定n个元素组成的序列：a₀,a₁,a₂,...,a_n,求此序列中和最大的连续子序列。
如：序列为 1，3，-8，2，6，-2，4，-2，1 ，求得子序列为：2，6，-2，4 结果为10 。

      额，自己很久都没写过动态规划方面的题目了，上一次校赛那个矩阵连乘问题拿到手上一看就知道是动态规划方面的问题，但就是不晓得怎么写。但面试题目中有很多动态规划方面的题目层出不穷，所以，偶打算从最简单的动态规划方面写起。

      首先，还是写个暴力的呗。就是把序列的字串的和枚举出来。找出最大的一个即可。根据这个思路，代码很快出来了！

/******暴力求最大子段和*******/<br /> #include<stdio.h></p> <p>int maxSum(int a[], int n, int *begin, int *end)<br /> {<br /> int sum = -1000000, temp, i, j, k;</p> <p> for(i=0; i<n; ++i)<br /> {<br /> for(j=i+1; j<n; ++j)<br /> {<br /> temp = 0;<br /> for(k=i; k<=j; ++k)<br /> temp += a[k];<br /> if(temp > sum)<br /> {<br /> *begin = i;<br /> *end = j;<br /> sum = temp;<br /> }<br /> }<br /> }</p> <p> return sum;<br /> }</p> <p>int main()<br /> {<br /> int a[100], n, i;<br /> while(scanf("%d", &n) != EOF)<br /> {<br /> int bestBegin, bestEnd;//最大子序列的下表的开始位置和结束位置。<br /> for(i=0; i<n; ++i)<br /> scanf("%d", &a[i]);<br /> printf("bestBegin = %d, bestEnd = %d, The Subsequence MaxSum = %d./n", bestBegin, bestEnd, maxSum(a, n, &bestBegin, &bestEnd));<br /> }<br /> return 0;<br /> }<br />

      额，话说我暴力也还是出了一点小小的问题。当我输入测试数据 1 10的时候，结果给我返回一个结果：

      bestBegin = -858993460, bestEnd = -858993460, The Subsequence MaxSum = -1000000.偶一查maxSum函数，马上知道代码问题出哪里了，果断把第一个for循环前面j初始化为 j = i;OK，序列只有一个数也正常了。这个很幼稚的错误我特意列出来是提醒自己一下，无论觉得自己的Code多么正确，一定要用自己能想到的刁钻的测试数据去测试一下自己的代码。

      OK，来分析一下这个代码。呵呵，优点是简单易懂，只需要O(1)的空间。可是时间复杂度为O(n³)，显然，这么大的时间复杂度肯定是不行的，当n=1千万的时候，很难出结果了。那就慢慢优化呗~~~

      OK，注意到sum(a₀+a₁+a₂+……+a_j-1+a_j) = sum(a₀+a₁+a₂+……+a_j-1) +a_j ,那么，我们可以把maxSum函数做个小小的优化。代码如下：

int maxSum(int a[], int n, int *begin, int *end)<br /> {<br /> int sum = -1000000, temp, i, j;</p> <p> for(i=0; i<n; ++i)<br /> {<br /> temp = 0;<br /> for(j=i; j<n; ++j)<br /> {<br /> temp += a[j];<br /> if(temp > sum)<br /> {<br /> *begin = i;<br /> *end = j;<br /> sum = temp;<br /> }<br /> }<br /> }<br /> return sum;<br /> }

      这样，利用前面计算出来的结果，不重复计算，我们把时间复杂度从O(n³)降到了O(n²)。好了，接着再来优化吧。

      额，接下来是用分治的算法来降低复杂度。
      将a[1n]分成a[1n/2]和a[n/2+1n],则a[1n]的最大字段和有三种情况:
      (1)a[1n]的最大子段和与a[1n/2]的最大子段和相同
      (2)a[1n]的最大子段和与a[n/2n]的最大子段和相同
      (3)a[1n]的最大子段和为ai++aj,1<=i<=n/2,n/2+1<=j<=n

      相信这个思想大家都能看懂。偶就啥也不说了，根据这个思想，偶就把代码写出来了。

#include<stdio.h></p> <p>int maxSum(int a[],int left, int right)<br /> {<br /> int sum = -100000000;<br /> if(left == right-1)<br /> {<br /> return a[left];<br /> }<br /> else<br /> {<br /> int middle = (left + right) / 2;<br /> int leftSum = maxSum(a, left, middle);<br /> int rightSum = maxSum(a, middle, right);</p> <p> int i;</p> <p> int temp = 0, tempLeftSum = -100000000;<br /> for(i=middle-1; i>=left; --i)<br /> {<br /> temp += a[i];<br /> if(temp > tempLeftSum)<br /> {<br /> tempLeftSum = temp;<br /> }<br /> }</p> <p> temp = 0;<br /> int tempRightSum = -100000000;<br /> for(i=middle; i<right; ++i)<br /> {<br /> temp += a[i];<br /> if(temp > tempRightSum)<br /> {<br /> tempRightSum = temp;<br /> }<br /> }</p> <p> sum = tempLeftSum + tempRightSum;<br /> if(sum < leftSum)<br /> sum = leftSum;<br /> if(sum < rightSum)<br /> sum = rightSum;<br /> }<br /> return sum;<br /> }</p> <p>int main()<br /> {<br /> int a[100], n, i;<br /> while(scanf("%d", &n) != EOF)<br /> {<br /> for(i=0; i<n; ++i)<br /> scanf("%d", &a[i]);<br /> printf("The Subsequence MaxSum = %d./n", maxSum(a, 0, n));<br /> }<br /> return 0;<br /> }<br />

      终于把O(n³)，O(n²)的复杂度降到了O(nlog₂ⁿ)。呵呵，应该是一个不错的改进了。O(∩_∩)O哈哈~给自己鼓掌一下。还能不能降低时间复杂度呢？答案是肯定的！因为动态规划的思想还没有提到嘛。下面就用动态规划的思想把时间复杂度降到O(n)。

      额，以下思路来自《编程之美》。

      假设已经知道（a[1], a[2], ......a[n-1]）中最大的一段数组之和为sum[1]，并且你还知道（a[1], a[2], ......a[n-1]）包含a[1]的最大和的一段数组为start[1]，那么，毫无疑问，（a[0], a[1], a[2], ......a[n-1]）所求的最大的一段数组和为max(a[0], a[0]+start[1], sum[1])；由于这个问题无后效性，故根据该思路可以写出如下代码：

#include<stdio.h></p> <p>int max(int a, int b)<br /> {<br /> return a>b ? a:b;<br /> }</p> <p>int maxSum(int a[],int n)<br /> {<br /> int *sum = new int[n], *start = new int[n], i, temp;<br /> sum[n-1] = a[n-1];<br /> start[n-1] = a[n-1];</p> <p> for(i=n-2; i>=0; --i)<br /> {<br /> start[i] = max(a[i], a[i]+start[i+1]);<br /> sum[i] = max(start[i], sum[i+1]);<br /> }</p> <p> temp = sum[0];</p> <p> delete []sum;<br /> delete []start;</p> <p> return temp;<br /> }</p> <p>int main()<br /> {<br /> int a[100], n, i;<br /> while(scanf("%d", &n) != EOF)<br /> {<br /> for(i=0; i<n; ++i)<br /> scanf("%d", &a[i]);<br /> printf("The Subsequence MaxSum = %d./n", maxSum(a, n));<br /> }<br /> return 0;<br /> }<br />

      值得注意的是：maxSum函数的for循环里面不能写成max(a[i], a[i]+start[i+1], sum[i+1])（想想为什么？）。

      不过美中不足的是，虽然这段代码终于把时间复杂度降到了O(n),但我们又申请了两个额外的两个数组start[n], sum[n]。能不能把空降复杂度降到O(1)呢？我们来观察maxSum函数里面的两个递推式：

                    start[i] = max(a[i], a[i]+start[i+1]);
                    sum[i] = max(start[i], sum[i+1]);

      很显然，要是start[i+1]<0,那么start[i] = a[i], 而且，start[i+1]只有在计算start[i]时才使用，而sum[i+1]也只有在计算sum[i]的时候才使用。所以程序可做进一步改进，使空间复杂度将为O(1)。代码如下：

#include<stdio.h></p> <p>int max(int a, int b)<br /> {<br /> return a>b ? a:b;<br /> }</p> <p>int maxSum(int a[],int n)<br /> {<br /> int sum, start, i;<br /> sum = a[n-1];<br /> start = a[n-1];</p> <p> for(i=n-2; i>=0; --i)<br /> {<br /> start = max(a[i], a[i]+start);<br /> sum = max(start, sum);<br /> }</p> <p> return sum;<br /> }</p> <p>int main()<br /> {<br /> int a[100], n, i;<br /> while(scanf("%d", &n) != EOF)<br /> {<br /> for(i=0; i<n; ++i)<br /> scanf("%d", &a[i]);<br /> printf("The Subsequence MaxSum = %d./n", maxSum(a, n));<br /> }<br /> return 0;<br /> }

      OK，该算法不仅改进了空间，而且代码也不长。基本上算是完美了~~~当然，上面的代码是逆推出来的，可不可以顺推呢？当然是可以的，请看下面的代码：

#include<stdio.h></p> <p>int maxSum(int a[],int n)<br /> {<br /> int sum = -10000000, temp = sum, i;<br /> for(i=0; i<n; ++i)<br /> {<br /> if(temp>0)<br /> temp += a[i];<br /> else<br /> temp = a[i];<br /> sum = temp > sum ? temp : sum;<br /> }<br /> return sum;<br /> }</p> <p>int main()<br /> {<br /> int a[100], n, i;<br /> while(scanf("%d", &n) != EOF)<br /> {<br /> for(i=0; i<n; ++i)<br /> scanf("%d", &a[i]);<br /> printf("The Subsequence MaxSum = %d./n", maxSum(a, n));<br /> }<br /> return 0;<br /> }

      好了，这段代码我觉得是所有代码里面最完美的了，不仅空间复杂度时间复杂度都为O(n)，而且代码短小。最后留两个作业给自己和看过的同学思考：①如果要返回最大子数组的位置，算法该如何改变？（其实偶在暴力法里面写了）还能保持O(n)的时间复杂度么？②如果数组首位相连，代码该如何写？