เพิ่มค่าสูงสุดของค่าต่ำสุดใน K ช่วงย่อยติดต่อกันใน C++

งานคือแบ่งอาร์เรย์ arr[] เป็น K ช่วงย่อยติดต่อกัน (consecutive sub-arrays) และหาค่าสูงสุดที่เป็นไปได้ของ "ค่าสูงสุดของค่าต่ำสุด" ของ K ช่วงย่อยเหล่านั้น

ตัวอย่าง

ตัวอย่างที่ 1

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

Output: 9

คำอธิบาย: แบ่งเป็น 3 ช่วง: {2,8,4,3}, {9}, {1,5}

ค่าต่ำสุดแต่ละช่วง: 2, 9, 1 → ค่าสูงสุดของค่าเหล่านี้ = 9

ตัวอย่างที่ 2

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

Output: 11

K=1 → ช่วงเดียว = อาร์เรย์ทั้งหมด → ค่าต่ำสุด = 1 แต่ output บอก 11? สังเกต: โจทย์อาจหมายถึง "ค่าสูงสุดของค่าต่ำสุด" แต่ K=1 ค่าต่ำสุดคือ min ของอาร์เรย์ทั้งหมด ตัวอย่าง output 11 ไม่สอดคล้อง → น่าจะเป็น ค่าสูงสุดของอาร์เรย์ (max) เมื่อ K=1

ข้อสังเกตสำคัญ (Key Insight)

ปัญหานี้มี 3 กรณีหลัก:

กรณี 1: K = 1

มีแค่ 1 ช่วง = อาร์เรย์ทั้งหมด → "ค่าต่ำสุดของช่วง" = min ของอาร์เรย์ → "ค่าสูงสุดของค่าต่ำสุด" = min ของอาร์เรย์

แต่ตัวอย่าง output ให้ 11 (max) → โจทย์จริงอาจเป็น: หา max ของ min แต่ K=1 ให้ max ของอาร์เรย์ (อาจเป็นข้อผิดพลาดในโจทย์ต้นฉบับ)

กรณี 2: K = 2

แบ่งเป็น 2 ช่วง: prefix และ suffix ต้องหาจุดแบ่งที่ทำให้ max(min(prefix), min(suffix)) สูงสุด

• คำนวณ prefixMin[i] = min จาก index 0 ถึง i
• คำนวณ suffixMin[i] = min จาก index i ถึง n-1
• ลองจุดแบ่งทุกจุด: maxVal = max(maxVal, max(prefixMin[i], suffixMin[i+1]))

กรณี 3: K ≥ 3

สามารถแยกองค์ประกอบ มากที่สุด (max element) ออกมาเป็นช่วงย่อยเดี่ยวได้เสมอ (เพราะมี K ≥ 3 ช่วง จัดช่วงอื่นๆ ไปได้) → คำตอบคือ max ของอาร์เรย์

ตัวอย่างโค้ด (แก้ไขจากต้นฉบับ)

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

int maxOfMinOfKSubarrays(const vector<int>& arr, int K) {
    int n = arr.size();
    if (n == 0) return 0;
    
    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());
    
    if (K == 1) {
        return minVal;  // หรือ maxVal ตามการตีความโจทย์
    } else if (K >= 3) {
        return maxVal;
    } else {  // K == 2
        vector<int> prefixMin(n), suffixMin(n);
        prefixMin[0] = arr[0];
        for (int i = 1; i < n; i++)
            prefixMin[i] = min(prefixMin[i-1], arr[i]);
        
        suffixMin[n-1] = arr[n-1];
        for (int i = n-2; i >= 0; i--)
            suffixMin[i] = min(suffixMin[i+1], arr[i]);
        
        int ans = INT_MIN;
        for (int i = 0; i < n-1; i++) {
            ans = max(ans, max(prefixMin[i], suffixMin[i+1]));
        }
        return ans;
    }
}

int main() {
    vector<int> arr = {9, 4, 12, 5, 6, 11};
    int K = 2;
    cout << "Result: " << maxOfMinOfKSubarrays(arr, K) << endl;
    return 0;
}

ผลลัพธ์

Result: 11

K=2: prefixMin={9,4,4,4,4,4}, suffixMin={4,4,5,5,6,11} → max ของ max(prefixMin[i], suffixMin[i+1]) = 11

สรุป Logic