分治算法--最大值最小值、最大值次大值问题-蒲公英云

分治算法--最大值最小值、最大值次大值问题

最大值最小值问题

// 分治法求解最大值和最小值问题
void MaxMin(int a[], int low, int high, int &Max, int &Min) {
    if(low == high) {
     // 只有一个元素
        Max = a[low];
        Min = INF;
    } else if(low == high-1) {
     // 只有两个元素
        Max = max(a[low], a[high]);
        Min = min(a[low], a[high]);
    } else {
        int mid = (low + high)/2; // 分为两半
        int lmax, lmin; // 左半边第一大、第二大
        MaxMin(a, low, mid, lmax, lmin);
        int rmax, rmin; // 右半边第一大、第二大
        MaxMin(a, mid+1, high, rmax, rmin);
        // 左半边、右半边再进行比较
        Max = max(lmax, rmax);
        Min = min(lmin, rmin);
    }
}

最大值、次大值问题

// 用分治法查找序列中的最大值和次大值
void max1max2(int a[], int low, int high, int &max1, int &max2) {
    if(low == high) {
     // 只有一个元素
        max1 = a[low];
        max2 = INF;
    } else if(low == high-1) {
     // 只有两个元素
        max1 = max(a[low], a[high]);
        max2 = min(a[low], a[high]);
    } else {
        int mid = (low + high)/2; // 分为两半
        int lmax1, lmax2; // 左半边第一大、第二大
        max1max2(a, low, mid, lmax1, lmax2);
        int rmax1, rmax2; // 右半边第一大、第二大
        max1max2(a, mid+1, high, rmax1, rmax2);
        // 左半边、右半边再进行比较
        if(lmax1 > rmax1) {
            max1 = lmax1;
            max2 = max(lmax2, rmax1);
        } else {
            max1 = rmax1;
            max2 = max(rmax2, lmax1);
        }
    }
}