Time Limit: 10MS
Memory Limit: 400KB
Submit
Statistic
Problem 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
一行输出两个整数，之间以空格间隔输出：
第一个整数为所求的最大子段和；
第二个整数为用分治递归法求解最大子段和时，递归函数被调用的总次数。
Example Input
6
-2 11 -4 13 -5 -2
Example Output
20 11
思路:分治递归法实际上就是考察递归和归并的算法，对前半个区间递归 后半个区间递归，再与第三者合区间相比较找最大子段和的值
#include <iostream>
#include <cstdio>
#define MAX 50011
using namespace std;
int count; //全局变量 表示调用递归的次数
typedef int element;
typedef struct
{
element *elem;
int len;
}list;
void Inilist(list &L,int n)
{
L.elem=new int[MAX];
L.len=0;
}
void Createlist(list &L,int n)
{
for(int i=0;i<n;i++)
scanf("%d",&L.elem[i]);
L.len=n;
}
int MAX_num(list &L,int left,int right)
{
count++;
int max_num;
if(left==right) //递归中递推的边界(此时代表只有一个数)
return L.elem[left]>=0?L.elem[left]:0;
else
{
int mid=(left+right)/2;
int leftmax=MAX_num(L,left,mid); //前半个区间递归
int rightmax=MAX_num(L,mid+1,right); //后半个区间调用
int max1=0;
int num1=0;
for(int i=mid;i>=left;i--)
{
num1+=L.elem[i];
if(max1<num1)
max1=num1;
}
int max2=0,num2=0;
for(int i=mid+1;i<=right;i++)
{
num2+=L.elem[i];
if(max2<num2)
max2=num2;
}
max_num=max1+max2; //找出前半个区间的最大子段和、后半个区间的最大子段和和合区间三者的最大值
if(leftmax>max_num)
max_num=leftmax;
if(rightmax>max_num)
max_num=rightmax;
}
return max_num;
}
int main()
{
int n;
scanf("%d",&n);
list node;
Inilist(node,n);
Createlist(node,n);
count=0;
int k=MAX_num(node,0,n-1);
printf("%d %d\n",k,count);
return 0;
}
//如果想用cin、cout输入输出流的话 可以参考下面
/*
int main()
{ //对此语句感兴趣的同学，大家可以在网上仔细了解一下
std::ios::sync_with_stdio(false); //这个语句可以取消cin与stdio的同步
std::cin.tie(0); //通过tie(0)(o表示NULL)来接触cin与cout的绑定，进一步加快执行效率
int n;
cin>>n;
list node;
Inilist(node,n);
Createlist(node,n);
count=0;
int k=MAX_num(node,0,n-1);
cout<<k<<" "<<count<<endl;
return 0;
}
*/
