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

雨点打透心脏的1/2处 2024-04-23 20:14 114阅读 0赞

#### 最大值最小值问题 ####

// 分治法求解最大值和最小值问题
    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);
            }
        }
    }

####  ####