Divide and Conquer memecah masalah besar menjadi sub-masalah yang lebih kecil, menyelesaikan masing-masing secara independen, lalu menggabungkan hasilnya.

3 langkah:

1. Divide — pecah masalah jadi sub-masalah
2. Conquer — selesaikan sub-masalah (rekursif)
3. Combine — gabungkan hasil

Kamu sudah melihat D&C di:

• Merge Sort — divide array, sort masing-masing, merge
• Quick Sort — partition, sort kiri & kanan
• Binary Search — cari di separuh data

Contoh: Maximum subarray (Kadane vs D&C)

// D&C approach — O(n log n)
function maxSubarrayDC(arr, left = 0, right = arr.length - 1) {
  if (left === right) return arr[left];

  const mid = Math.floor((left + right) / 2);

  const leftMax = maxSubarrayDC(arr, left, mid);
  const rightMax = maxSubarrayDC(arr, mid + 1, right);
  const crossMax = maxCrossingSum(arr, left, mid, right);

  return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossingSum(arr, left, mid, right) {
  let leftSum = -Infinity, sum = 0;
  for (let i = mid; i >= left; i--) {
    sum += arr[i];
    leftSum = Math.max(leftSum, sum);
  }

  let rightSum = -Infinity;
  sum = 0;
  for (let i = mid + 1; i <= right; i++) {
    sum += arr[i];
    rightSum = Math.max(rightSum, sum);
  }

  return leftSum + rightSum;
}

Contoh: Power function — O(log n)

// Biasa: 2^10 = 2*2*2*2*2*2*2*2*2*2 → 10 operasi
// D&C:  2^10 = (2^5)^2 → 2^5 = (2^2)^2 * 2 → jauh lebih sedikit
function power(base, exp) {
  if (exp === 0) return 1;
  if (exp % 2 === 0) {
    const half = power(base, exp / 2);
    return half * half;
  }
  return base * power(base, exp - 1);
}

D&C vs DP:

• D&C: sub-masalah independen (tidak overlap)
• DP: sub-masalah overlap (dihitung ulang)

🎭 Analogi sehari-hari: Mau angkat batu besar berdua. Susah. Bagi jadi 2 batu kecil — masing-masing diangkat satu orang. Lebih mudah. Kalau masih berat, bagi lagi. Setelah masing-masing diangkat, gabungkan ke truk. Itulah Divide & Conquer.

💡 Master Theorem (intuisi): Jika T(n) = a × T(n/b) + O(n^c) (a sub-masalah, masing-masing n/b, combine O(n^c)):

• c = log_b(a) → O(n^c × log n) (Merge Sort)
• c < log_b(a) → O(n^log_b(a))
• c > log_b(a) → O(n^c)

Mengapa Merge Sort O(n log n)? a=2, b=2, c=1, log₂2=1=c → n^1 × log n = n log n.

⚠️ Jebakan umum:

• Recursion overhead untuk n kecil — kebanyakan D&C-nya makan biaya konstan. Fallback ke iteratif untuk base case kecil
• Slice/copy data di setiap recursion = boros memori. Pakai index range
• Salah base case = infinite recursion atau salah hasil
• Confuse D&C dengan DP — kalau subproblem overlap, DP lebih cocok

🎯 Pola "ini D&C":

• Sorting (Merge Sort, Quick Sort)
• Searching (Binary Search)
• Operasi matriks (Strassen multiplication)
• Closest pair of points in 2D
• Power function dalam O(log n)
• Karatsuba multiplication untuk angka besar

🧪 Tebakan cepat: Power 2^20 naive O(20) ops. D&C: log₂20 ≈ 5 calls. 4x lebih sedikit untuk n kecil, 1000x untuk n besar.

TL;DR: Divide & Conquer = bagi → recurse → combine. Powerful kalau subproblem independen. Master Theorem analyze complexity. Foundation merge/quick sort, binary search, dan banyak optimasi log n.