李雪健代码

#include<iostream>
#include<vector>
using namespace std;

int partition(vector<int>& v, int left, int right){
    int pivot = v[left];
    while(left < right){
        while(left < right && v[right] < pivot){
            right --;
        }
        v[left] = v[right];
        while(left < right && v[left] > pivot){
            left ++;
        }
        v[right] = v[left];
    }
    v[left] = pivot;
    return left;
}

int top_4_sum(vector<int>& v, int left, int right){
    int position = partition(v, left, right);
    cout << position << " " << left << " " << right << endl;
    if (position == 3){
        int sum = 0;
        for (int i = 0; i < 4; i ++){
            cout << v[i] << " ";
            sum += v[i];
        }
        cout << endl;
        return sum;
    }
    if (position < 4){
        return top_4_sum(v, position + 1, right);
    }
    else{
        return top_4_sum(v, left, position - 1);
    }
}

int main(){
    vector<int> v = {0, 4, 2, 3, 6, 1, 7, 8};
    // cout << partition(v, 0, v.size() - 1) << endl; // supposed to be 3
    // for (int i : v){
    //     cout << i << " ";
    // }
    // cout << endl;
    cout << top_4_sum(v, 0, v.size() - 1) << endl; // supposed to be 25
    return 0;
}