Phần tử giữa lớn nhất sau khi xóa đúng K phần tử trong C++

Cho mảng size N và số K. Xóa đúng K phần tử sao cho phần tử giữa (median) của mảng còn lại lớn nhất.

Thuật toán

• Sau khi xóa K phần tử, còn N-K phần tử. Vị trí giữa (1-based) là (N-K+1)/2.
• Trong mảng gốc đã sắp xếp, phần tử giữa có thể nằm trong khoảng từ chỉ số low = (N-K+1)/2 đến high = low + K (0-based: low-1 đến high-1).
• Trả về max trong khoảng đó.

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

int maximum_middle_value(int n, int k, int arr[]) {
    int ans = -1;
    int low = (n + 1 - k) / 2;
    int high = low + k;
    for (int i = low; i <= high; i++)
        ans = max(ans, arr[i-1]);
    return ans;
}

int main() {
    int n = 5, k = 2;
    int arr[] = {9, 5, 3, 7, 10};
    cout << maximum_middle_value(n, k, arr) << endl;
    n = 9; k = 3;
    int arr1[] = {2, 4, 3, 9, 5, 8, 7, 6, 10};
    cout << maximum_middle_value(n, k, arr1) << endl;
    return 0;
}

Đầu ra

7 9