-
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
一行輸出兩個整數，之間以空格間隔輸出：
第一個整數為所求的最大子段和；
第二個整數為用分治遞回法求解最大子段和時，遞回函式被呼叫的總次數，
Sample Input
6
-2 11 -4 13 -5 -2
Sample Output
20 11
-
解題思路
以中間元素為界，將一個序列分為左邊、右邊，那么求一個序列的最大子段和就有三種情況：① 序列左邊的元素具有最大子段和；② 序列右邊元素具有最大子段和；③ 從中間向兩端擴展的子段具有最大子段和，
-
代碼實作
#include <bits/stdc++.h>
using namespace std;
int n; //整數序列中的資料元素個數
int number[50001]; //整數序列中的資料元素
int Max=INT_MIN; //最大子段和
int count1=0; //遞回函式被呼叫的總次數
int maxSum(int l,int r)
{
int sum=0;
count1++;
if(l==r) //如果整數序列中只有一個元素
{
if(number[l]>0) //非負，其本身就是最大子段和
sum=number[l];
else //為負，最大子段和等于 0
sum=0;
}
else //整數序列中至少有兩個元素
{
int mid=(l+r)/2;
int leftSum=maxSum(l,mid); //情況1：最大欄位和全部取左邊元素
int rightSum=maxSum(mid+1,r); //情況2：最大欄位和全部取右邊元素
int tempSum,s1,s2; //情況3：最大子段從中間向兩端擴展
tempSum=s1=0; //一定要賦初值，且兩者相等
for(int i=mid;i>=l;i--) //求從中間元素到最左端的最大子段和s1
{
tempSum+=number[i];
if(tempSum>s1)
s1=tempSum;
}
tempSum=s2=0;
for(int i=mid+1;i<=r;i++) //求從中間元素到最右端的最大子段和s2
{
tempSum+=number[i];
if(tempSum>s2)
s2=tempSum;
}
sum=s1+s2; //sum即為從中間向兩端擴展的最大子段和
sum=max(sum,leftSum); //上述三種情況求最大值
sum=max(sum,rightSum); //上述三種情況求最大值
}
return sum;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>number[i];
Max=maxSum(1,n);
cout<<Max<<" "<<count1<<endl;
return 0;
}
- 運行結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/236139.html
標籤：其他
上一篇：XDOJ 307 括號匹配的檢驗