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

xiaoxiao2021-02-28  15

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

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; } */
转载请注明原文地址: https://www.6miu.com/read-1150009.html

最新回复(0)