脚本宝典收集整理的这篇文章主要介绍了顺序表应用7：最大子段和之分治递归法，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
给定n(1~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。
注意：本题目要求用分治递归法求解，除了需要输出最大子段和的值之外，还需要输出求得该结果所需的递归调用总次数。
Input 第一行输入整数n(1~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;
}
}
以上是脚本宝典为你收集整理的顺序表应用7：最大子段和之分治递归法全部内容，希望文章能够帮你解决顺序表应用7：最大子段和之分治递归法所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。