Menyusun Pendekatan

Memahami soal hanyalah setengah pekerjaan; setengah lainnya adalah menyusun pendekatan yang benar. Banyak pemula melompat langsung ke solusi optimal dan terjebak pada detail yang belum matang. Pendekatan yang lebih aman adalah memulai dari brute force sebagai baseline, lalu mengidentifikasi pola, mengoptimasi, dan memverifikasi dengan contoh kecil. Pada Chapter ini kita akan menerapkan kerangka empat langkah tersebut pada satu soal nyata: mencari jumlah maksimum subarray berukuran tepat k yang ditambah syarat “tidak boleh dua window berdekatan”.

Kerangka Empat Langkah #

Aturan: Jangan Lompat ke Optimal #

Solusi optimal jarang muncul pertama. Brute force memberi kita baseline yang pasti benar — untuk verifikasi solusi cepat di tahap lanjut. Bahkan bila brute force TLE, baseline ini tetap berguna untuk n kecil selama pengembangan.

Mekanisme: Bagaimana Pola Ditemukan #

Pola muncul ketika kita melihat overlap antar subproblem atau struktur pada perhitungan. Contoh:

• Bila perhitungan window i dan window i+1 memuat banyak elemen yang sama → pola sliding window.
• Bila f(n) dapat diturunkan dari f(n-1) → pola DP atau greedy.
• Bila jawaban monoton terhadap suatu parameter → pola binary search pada jawaban.

Studi Kasus: Maksimum Dua Subarray Tidak Berdekatan #

Soal #

Diberikan array a berukuran n dan integer k. Pilih dua subarray masing-masing berukuran tepat k sehingga jumlah elemennya maksimum, dengan syarat kedua subarray tidak saling tumpang tindih (boleh bersebelahan). Kembalikan jumlah total maksimum. Constraint: 2 ≤ n ≤ 10^5, 1 ≤ k ≤ n/2.

Langkah 1 — Brute Force #

Untuk setiap pasangan (i, j) dengan i + k ≤ j atau j + k ≤ i, hitung jumlah a[i..i+k-1] + a[j..j+k-1] dan ambil maksimum. Kompleksitas: O(n²·k) — sangat lambat untuk n = 10^5, tetapi baseline yang benar.

Langkah 2 — Identifikasi Pola #

Perhatikan bahwa kita perlu jumlah setiap window berukuran k — ini bisa dihitung sekali saja dengan sliding window O(n). Setelah itu, untuk setiap indeks batas m, kita butuh “jumlah window maksimum di kiri m” dan “jumlah window maksimum di kanan m”. Pola: precompute prefix-max dan suffix-max.

Langkah 3 — Optimasi #

Hitung array win[i] = jumlah a[i..i+k-1] untuk semua i valid (O(n) sliding window). Lalu:

• pref[i] = maksimum win[0..i]
• suff[i] = maksimum win[i..n-k]

Untuk setiap titik potong m, jawaban kandidat adalah pref[m] + suff[m+k] (window kiri di ≤ m, window kanan di ≥ m+k agar tidak tumpang tindih). Iterasi semua m valid: O(n).

Langkah 4 — Verifikasi #

Bandingkan hasil optimasi dengan brute force untuk n kecil. Bila cocok, kita yakin solusi benar.

Kode: Implementasi Empat Langkah #

#include <iostream>
#include <vector>
#include <algorithm>

long long brute(const std::vector<int>& a, int k) {
    int n = static_cast<int>(a.size());
    auto sum = [&](int i) {
        long long s = 0;
        for (int t = 0; t < k; ++t) s += a[i + t];
        return s;
    };
    long long best = 0;
    for (int i = 0; i + k <= n; ++i) {
        for (int j = i + k; j + k <= n; ++j) {
            best = std::max(best, sum(i) + sum(j));
        }
    }
    return best;
}

long long optimal(const std::vector<int>& a, int k) {
    int n = static_cast<int>(a.size());
    int m = n - k + 1;  // jumlah window
    std::vector<long long> win(m);
    long long cur = 0;
    for (int i = 0; i < k; ++i) cur += a[i];
    win[0] = cur;
    for (int i = 1; i < m; ++i) {
        cur += a[i + k - 1] - a[i - 1];
        win[i] = cur;
    }
    std::vector<long long> pref(m), suff(m);
    pref[0] = win[0];
    for (int i = 1; i < m; ++i) pref[i] = std::max(pref[i-1], win[i]);
    suff[m-1] = win[m-1];
    for (int i = m - 2; i >= 0; --i) suff[i] = std::max(suff[i+1], win[i]);

    long long best = 0;
    for (int cut = 0; cut + 1 < m; ++cut) {
        // window kiri di [0..cut], window kanan di [cut+k..m-1]
        if (cut + k < m) {
            best = std::max(best, pref[cut] + suff[cut + k]);
        }
    }
    return best;
}

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5, 6, 7, 8};
    int k = 2;
    std::cout << "brute   = " << brute(a, k) << '\n';
    std::cout << "optimal = " << optimal(a, k) << '\n';

    std::vector<int> b = {5, 1, 9, 3, 7, 2, 8, 4, 6};
    k = 3;
    std::cout << "brute   = " << brute(b, k) << '\n';
    std::cout << "optimal = " << optimal(b, k) << '\n';
    return 0;
}

Output yang Dihasilkan:

brute   = 26
optimal = 26
brute   = 37
optimal = 37

1. Fungsi brute: cek semua pasangan (i, j) yang tidak tumpang tindih. Kompleksitas O(n²·k). Hanya untuk verifikasi.
2. Lambda sum(i): hitung jumlah window mulai indeks i. Didefinisikan inline via [&].
3. Baris cur += a[i + k - 1] - a[i - 1];: sliding window untuk membangun win[] dalam O(n). Lihat Chapter Sliding Window untuk detail.
4. Baris pref[i] = std::max(pref[i-1], win[i]);: prefix-max. pref[i] = window maksimum di rentang [0..i].
5. Baris suff[i] = std::max(suff[i+1], win[i]);: suffix-max, dihitung dari kanan ke kiri.
6. Baris if (cut + k < m): jamin window kanan tidak tumpang tindih dengan window kiri. cut + k adalah indeks window pertama yang sepenuhnya setelah window kiri cut.
7. Baris best = std::max(best, pref[cut] + suff[cut + k]);: kombinasi terbaik — window kiri maksimum di kiri cut, window kanan maksimum di kanan cut+k-1.
8. Hasil 26 untuk a={1..8}, k=2: window {7,8}=15 + {5,6}=11 = 26. Sesuai brute force.
9. Hasil 37 untuk b, k=3: window {9,3,7}=19 + {8,4,6}=18 = 37. Sesuai brute force.

Daftar Periksa Optimasi yang Sering Berguna #

Ringkasan #

• Kerangka empat langkah: brute force → pola → optimasi → verifikasi. Jangan lompat ke optimal sebelum punya baseline yang benar.
• Brute force bukan sampah — ia adalah alat verifikasi. Simpan untuk n kecil selama debugging.
• Pola diidentifikasi dari overlap (sliding window), substructure (DP), atau monotonisitas (binary search pada jawaban).
• Studi kasus “maksimum dua subarray tidak berdekatan” memperlihatkan transformasi O(n²·k) → O(n) memanfaatkan precompute prefix-max + suffix-max.
• Selalu uji optimasi terhadap brute force pada beberapa contoh kecil sebelum submit.