摄影公司网站开发,牛牛网站建设,东莞设计制作网站制作,互联网建设网站Problem Description 给定n(1n50000)个整数#xff08;可能为负数#xff09;组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]a[i1]…a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0#xff0c;依此定义#xff0c;所求的最优值为#xff1a; Max{… Problem Description 给定n(1n50000)个整数可能为负数组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]a[i1]…a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0依此定义所求的最优值为 Max{0,a[i]a[i1]…a[j]},1ijn。 例如当a[1],a[2],a[3],a[4],a[5],a[6](-2,11,-4,13,-5,-2)时最大子段和为20。 注意本题目要求用分治递归法求解除了需要输出最大子段和的值之外还需要输出求得该结果所需的递归调用总次数。 递归调用总次数的获得可以参考以下求菲波那切数列的代码段中全局变量count的用法 #include int count0; int main() { int n,m; int fib(int n); scanf(%d,n); mfib(n); printf(%d %d\n,m,count); return 0; } int fib(int n) { int s; count; if((n1)||(n0)) return 1; else sfib(n-1)fib(n-2); return s; } Input 第一行输入整数n(1n50000)表示整数序列中的数据元素个数 第二行依次输入n个整数对应顺序表中存放的每个数据元素值。 Output 一行输出两个整数之间以空格间隔输出 第一个整数为所求的最大子段和 第二个整数为用分治递归法求解最大子段和时递归函数被调用的总次数。 Example Input 6
-2 11 -4 13 -5 -2 Example Output 20 11 #includeiostream #includecstdio using namespace std; int count0; int a[50010]; int Max(int a[],int l,int r) { int k,sum0; count; if(lr) return a[1]0?a[1]:0; else { int mid(lr)/2; int lMaxMax(a,l,mid); int rMaxMax(a,mid1,r); int max10; int lefts0; for(kmid;kl;k--) { leftsa[k]; if(leftsmax1) max1lefts; } int max20; int rights0; for(kmid1;kr;k) { rightsa[k]; if(rightsmax2) max2rights; } summax1max2; if(sumlMax) sumlMax; if(sumrMax) sumrMax; } return sum; } int main() { int n,max; scanf(%d,n); for(int i1;in;i) scanf(%d,a[i]); maxMax(a,1,n); if(max0) max0; printf(%d %d\n,max,count); return 0; } #include iostream #includecstdio using namespace std; int main() { int sum0,max0; int n; scanf(%d,n); int a[100001]; for(int i0;in;i) { scanf(%d,a[i]); suma[i]; if(sum0) sum0; if(summax) maxsum; } printf(%d\n,max); }
