题目：

最大子列和问题

问题描述：

给定K个整数组成的序列{ N​1​​, N​2​​, ..., N​K​​ }，“连续子列”被定义为{ N​i​​, N​i+1​​, ..., N​j​​ }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据1：与样例等价，测试基本正确性；
• 数据2：102个随机整数；
• 数据3：103个随机整数；
• 数据4：104个随机整数；
• 数据5：105个随机整数；

输入格式:

输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:

6

-2 11 -4 13 -5 -2

输出样例:

20

 

算法描述：

本题采用分治法的思想，将原问题一分为二，分别求取左子列和右子列的最大子列和，另外，还有一种比较特殊的情况，就是可能所求的子列横跨中间元素，这种情况要单独拿出来讨论。

最后比较三者的值，返回其最大值。

 

算法时间及空间复杂度分析：

 1 #include <iostream>
 2  using namespace std;
 3  
 4  void input(int a[],int num)
 5  {
 6      for(int i=0;i<num;i++)
 7      cin >> a[i];
 8  }
 9  
10  int compare(int lmax,int rmax,int mmax)
11  {
12      int max=0;
13      if(lmax>=rmax && lmax>=mmax) max=lmax;
14      else if(rmax>=lmax && rmax>=mmax) max=rmax;
15      else max=mmax;
16      return max;
17  }
18  
19  int maxsum(int a[], int left, int right)
20  {
21      //if(left>right) return 0;
22      if(left==right)
23      {
24          if(a[left]>0) return a[left];
25          else return 0;
26      }
27      int mid=(left+right)/2;
28      int lmax=maxsum(a,left,mid);
29      int rmax=maxsum(a,mid+1,right);
30      int lmmax=0;
31      int lsum=0;
32      for(int i=mid;i>=left;i--)
33      {
34          lsum+=a[i];
35         if(lsum>lmmax) lmmax=lsum; 
36      }
37      int rmmax=0;
38      int rsum=0;
39      for(int i=mid+1;i<=right;i++)
40      {
41          rsum+=a[i];
42         if(rsum>rmmax) rmmax=rsum; 
43      }
44      
45      int mmax=lmmax+rmmax;
46      return compare(lmax,rmax,mmax);
47  }
48  
49  int main()
50  {
51      int num;
52      cin >> num;
53      int *a=new int[num+1];
54      input(a,num);
55      cout << maxsum(a,0,num-1);
56      delete []a;
57      return 0;
58  }

时间复杂度：该算法的时间分为分治求左右子列和与跨越中间元素的子列的和。其中，分治的问题规模为原问题的一半，则时间复杂度为2T（n/2）,后者从中间元素出发，分别扫描左右两边的数，故时间复杂度为O（n）.根据主定理T（n）=2T（n/2）+O（n）=O（n log n）。

空间复杂度：该算法只用到了辅助变量，故空间复杂度为O（1）。

 

心得体会：

我觉得分治法的难点在于找到问题规模最小到能求解的情况，并且在写递归函数的时候很容易绕晕。通过本题的练习，更加清晰地理解了分治法的思想。另外，与同伴的结对编程小笼包有所提高。