Tối đa hóa giá trị lớn nhất trong các giá trị nhỏ nhất của K mảng con liên tiếp trong C++

Cho mảng arr[] và số K. Nhiệm vụ: chia mảng thành K mảng con liên tiếp (consecutive sub-arrays) sao cho giá trị lớn nhất trong các giá trị nhỏ nhất của K mảng con đó là lớn nhất có thể.

Ví dụ 1

Input

arr[] = {2, 8, 4, 3, 9, 1, 5}, K = 3

Output – 9

Giải thích: Chia thành 3 mảng con: {2,8,4,3}, {9}, {1,5}.

Giá trị nhỏ nhất của mỗi mảng: 2, 9, 1. Giá trị lớn nhất trong đó: 9.

Ví dụ 2

Input

arr[] = {8, 4, 1, 9, 11}, K = 1

Output – 11

Giải thích: K=1 → toàn bộ mảng là 1 mảng con. Min = 1, Max = 1? Wait... K=1 nghĩa là không chia, min của cả mảng là 1. Nhưng output là 11? Có lỗi trong ví dụ gốc. K=1 nên trả về min của mảng = 1.

Phân tích trường hợp

Bài toán chia thành 3 trường hợp:

1. K = 1: Không chia được. Mảng con duy nhất là cả mảng. Kết quả = min của cả mảng.
2. K = 2: Chia thành 2 phần: prefix và suffix. Cần tính prefix_min[i] và suffix_min[i]. Kết quả = max over i của max(prefix_min[i], suffix_min[i+1]).
3. K ≥ 3: Luôn có thể tách riêng phần tử lớn nhất của mảng thành 1 mảng con đơn lẻ. Kết quả = max của cả mảng.

Ví dụ code (xử lý đúng 3 trường hợp)

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

int maximizeMaxOfMins(const int* arr, int size, int K) {
    int Min = INT_MAX;
    int Max = INT_MIN;
    
    for (int i = 0; i < size; i++) {
        Min = min(Min, arr[i]);
        Max = max(Max, arr[i]);
    }
    
    if (K == 1) {
        return Min; // Toàn mảng, min là nhỏ nhất
    } else if (K >= 3) {
        return Max; // Tách max ra riêng
    } else { // K == 2
        // Tính prefix min và suffix min
        vector<int> left(size), right(size);
        left[0] = arr[0];
        right[size - 1] = arr[size - 1];
        
        for (int i = 1; i < size; i++) 
            left[i] = min(left[i - 1], arr[i]);
        for (int i = size - 2; i >= 0; i--) 
            right[i] = min(right[i + 1], arr[i]);
        
        int maxValue = INT_MIN;
        for (int i = 0; i < size - 1; i++) {
            maxValue = max(maxValue, max(left[i], right[i + 1]));
        }
        return maxValue;
    }
}

int main() {
    int arr[] = {9, 4, 12, 5, 6, 11};
    int size = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
    cout << "Result: " << maximizeMaxOfMins(arr, size, K) << endl;
    return 0;
}

Kết quả

Result: 11

Giải thích K=2: Mảng [9,4,12,5,6,11]. Prefix min: [9,4,4,4,4,4]. Suffix min: [4,4,5,5,6,11]. Thử các điểm cắt: - i=0: max(9,4)=9 - i=1: max(4,5)=5 - i=2: max(4,5)=5 - i=3: max(4,6)=6 - i=4: max(4,11)=11 ← MAX

Lưu ý: Code gốc có lỗi khai báo `dint Max` và logic K=1 trả về Min (đúng), nhưng ví dụ K=1 output 11 là sai (phải là 1).