顺序表应用7：最大子段和之分治递归法

Description

 给定n(1<=n<=50000)个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n。 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。

 

注意：本题目要求用分治递归法求解，除了需要输出最大子段和的值之外，还需要输出求得该结果所需的递归调用总次数。

 

递归调用总次数的获得，可以参考以下求菲波那切数列的代码段中全局变量count的用法：

#include int count=0; int main() {     int n,m;     int fib(int n);     scanf("%d",&n);     m=fib(n);     printf("%d %d\n",m,count);     return 0; } int fib(int n) {     int s;     count++;     if((n==1)||(n==0)) return 1;     else s=fib(n-1)+fib(n-2);     return s; }  

Input

第一行输入整数n(1<=n<=50000)，表示整数序列中的数据元素个数；

第二行依次输入n个整数，对应顺序表中存放的每个数据元素值。

Output

一行输出两个整数，之间以空格间隔输出：

第一个整数为所求的最大子段和；

第二个整数为用分治递归法求解最大子段和时，递归函数被调用的总次数。

Sample

Input 

6 -2 11 -4 13 -5 -2

Output 

20 11

 

#include <iostream> #include <cstdio> #include <cstring> using namespace std; /*** 将字段分为两段，计算左边最大子段和、右边最大子段和、 最后从中间向两边增加元素求整段的最大子段和 再比较三者大小，取最大值作为整端的最大子段和 ***/ int f(int *, int, int); int count; int arr[50005]; int main() { int n; count = 0; memset(arr, 0, sizeof(arr)); cin >> n; for(int i = 0; i < n; i++) { scanf("%d", &arr[i]);///此处用cin会超时，cin会比scanf慢 } n = f(arr, 0, n - 1); cout << n << " " << count << endl; return 0; } int f(int *arr, int l, int r) { count++;///每次进入该函数都增加一次记录的次数 if(l == r) {///如果左边界等于右边界，即此子段只有一个元素 if(arr[l] > 0) {///若该元素的值大于0，则返回该元素的值 return arr[l]; } else {///若该元素的值小于0，则返回0 return 0; } } else { int mid = (l + r) / 2;///记录子段中间位置的下标 int leftsum, rightsum;///该子段最大和、该子段左部最大和、右部最大和 leftsum = f(arr, l, mid);///计算该子段左部最大和 rightsum = f(arr, mid + 1, r);///计算该子段右部最大和 int left_s, right_s, s;///left_s、right_s记录从中间向两侧的最大和，s为计算用的临时变量 left_s = s = 0;///注意要初始化left_s 和 s for(int i = mid; i >= l; i--) { s += arr[i];///s从中间元素的值一直向左侧累加 if(s > left_s ) left_s = s;///若s的值大于left_s记录的最大和，则更新left_s } right_s= s = 0;///注意要初始化right_s和 s for(int i = mid + 1; i <= r; i++)///注意此处i = mid + 1，不要忘了+1！！！ { s += arr[i];///s从中间元素的值一直向右侧累加 if(s > right_s) right_s= s;///若s的值大于right_s记录的最大和，则更新right_s } int sum = left_s + right_s;///将左侧最大和 与 右侧最大和 合并，计算该子段总的最大和 int max_sum = sum;///将该子段总的最大和、左侧最大和、右侧最大和作比较 ///取三者最大值作为该子段的最大和 if(max_sum < leftsum) max_sum = leftsum; if(max_sum < rightsum) max_sum = rightsum; return max_sum; } }

关于cin和scanf的超时问题：

算法竞赛的时候用cin cout输入输出比用scanf printf慢多少？

https://www.zhihu.com/question/27831271/answer/38405256?utm_source=qq&utm_medium=social&utm_oi=785529237665886208

cin慢是有原因的，其实默认的时候，cin与stdin总是保持同步的，也就是说这两种方法可以混用，而不必担心文件指针混乱，同时cout和stdout也一样，两者混用不会输出顺序错乱。正因为这个兼容性的特性，导致cin有许多额外的开销，如何禁用这个特性呢？只需一个语句std::ios::sync_with_stdio(false);，这样就可以取消cin于stdin的同步了。

作者：曹雨 链接：https://www.zhihu.com/question/27831271/answer/38405256 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。