分治法求集合最大元，分治法集合

分治法求集合最大元，分治法集合

題目：輸入n  然後輸入n個整數，用分治法求這n個數中的最大元；

思路：把這列數分成兩半，遞歸下去，到只剩一個數時停止，返回這個數，如果不是一個數則返回分成的兩段數最大值的較大者；

實驗提示：在規模為n的數據元素集合中找出最大元。當n=2時，一次比較就可以找出兩個數據元素的最大元和最小元。當n>2時，可以把n個數據元素分為大致相等的兩半，一半有n/2個數據元素，而另一半有n/2個數據元素。 先分別找出各自組中的最大元，然後將兩個最大元進行比較，就可得n個元素的最大元

代碼如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <queue>
#include <vector>
using namespace std;

int calc(int a[],int l,int r)
{
    if(l==r) return a[l];
    return max(calc(a,l,(l+r)/2),calc(a,(l+r)/2+1,r));
}

int main()
{
    int a[1005];
    int n;
    cout<<"數列長度： "<<endl;
    scanf("%d",&n);
    if(n==0) {puts("數列長度不能為0！"); return 0;}
    cout<<"請輸入數列： "<<endl;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);

    printf("這個數列的最大元為： %d\n",calc(a,0,n-1));
    return 0;
}