<ol><li><h1>Rumusan Soal<br></h1><p>Diberikan sebuah array integer nums berukuran n (bisa berisi bilangan positif, nol, dan negatif). Cari <b>subarray kontigu</b> (elemen berurutan, tidak boleh lompat) yang memiliki <b>jumlah (sum) terbesar</b>, lalu kembalikan nilai jumlahnya.<br>Contoh:<br> </p><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> </div> <pre><code>nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]<br><br>Subarray dengan jumlah terbesar: [4, -1, 2, 1]<br>Jumlah = 4 + (-1) + 2 + 1 = 6<br><br>Output: 6</code></pre> </div><p><b>Catatan penting:<br></b></p><ul><li>Yang dicari adalah <b>subarray</b> (kontigu), bukan subset (boleh lompat).</li><li>Jika semua elemen negatif, kita tetap pilih <b>satu elemen terbesar</b> (misalnya [-5, -2, -7] ➙ -2)</li></ul><div> <div class="jump-break" data-jump-break="true"> <span class="jump-break__label"><br></span></div> </div></li><li><h1>Cara Paling Naif (Brute Force) - Sekilas<br></h1><p>Pendekatan awal (untuk memahami konsep):<br></p><ol><li><div>Ambil semua pasangan indeks i (sebagai awal) dan j (sebagai akhir).</div></li><li><div>Hituing jumlah elemen dario i sampai j.</div></li><li><div>Simpan nilai maksimum selama perulangan.</div></li></ol><p>Pseudocode ide dasarnya:<br> </p><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>maxSum = -∞<br>for i from 0 to n-1:<br> for j from i to n-1:<br> sum = 0<br> for k from i to j:<br> sum += nums[k]<br> maxSum = max(maxSum, sum)<br>return maxSum</code></pre> </div> <ul><li>Kompleksitas waktu: <strong data-start="1299" data-end="1308">O(n³)</strong> (karena tiga loop).</li><li>Bisa dioptimasi dengan prefix sum jadi <strong data-start="1370" data-end="1379">O(n²)</strong>, tapi masih lambat untuk <code data-start="1405" data-end="1408">n</code> besar.</li></ul><div>Karena itu kita butuh cara yang <strong data-start="1449" data-end="1457">O(n)</strong> → di sinilah <strong data-start="1471" data-end="1493">Kadane’s Algorithm</strong> dipakai.</div><p> </p><div class="jump-break" data-jump-break="true"> <span class="jump-break__label"><br></span> </div></li><li><h1>Intuisi Kadane's Algorithm<br></h1><p data-start="1543" data-end="1560">Idenya sederhana:</p> <blockquote data-start="1562" data-end="1791"> <p data-start="1564" data-end="1791">Kalau <strong data-start="1570" data-end="1587">sum sementara</strong> yang kita punya sudah negatif, menambahkannya ke elemen berikutnya itu <strong data-start="1659" data-end="1682">tidak akan membantu</strong> — malah membuat jumlah jadi lebih kecil.<br data-start="1723" data-end="1726"> Jadi, kalau sudah negatif, <strong data-start="1755" data-end="1764">reset</strong> saja di elemen berikutnya.</p> </blockquote> <p data-start="1793" data-end="1848">Kita jalan dari kiri ke kanan sambil menjaga dua nilai:<br></p><ol><li data-start="1850" data-end="1915"><p data-start="1853" data-end="1915"><code data-start="1853" data-end="1865">currentSum</code> = jumlah subarray <strong data-start="1884" data-end="1915">berakhir di indeks saat ini</strong></p> </li><li data-start="1916" data-end="1994"> <p data-start="1919" data-end="1994"><code data-start="1919" data-end="1927">maxSum</code> = jumlah subarray <strong data-start="1946" data-end="1994">terbesar yang pernah kita temukan sejauh ini</strong></p> </li></ol>Setiap melihat nilai<code data-start="2017" data-end="2030">x = nums[i]</code>:<ul><li>Ada dua pilihan:<br><ul><li>Lanjutkan subarray sebelumnya: currentSum + x</li><li>Mulai subarray baru dari <code data-start="2133" data-end="2136">x</code> saja</li></ul></li></ul><div>Kita pilih yang lebih besar:<br><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>currentSum = max(x, currentSum + x)<br>maxSum = max(maxSum, currentSum)</code></pre></div><p data-start="2255" data-end="2273"><strong data-start="2255" data-end="2273">Kenapa begitu?</strong></p><ul data-start="2275" data-end="2522"><li data-start="2275" data-end="2388"> <p data-start="2277" data-end="2388">Jika <code data-start="2282" data-end="2298">currentSum + x</code> lebih besar → subarray terbaik yang berakhir di <code data-start="2347" data-end="2350">i</code> adalah dengan melanjutkan sebelumnya.</p> </li><li data-start="2389" data-end="2522"> <p data-start="2391" data-end="2522">Jika <code data-start="2396" data-end="2399">x</code> lebih besar → berarti <code data-start="2422" data-end="2434">currentSum</code> sebelumnya <strong data-start="2446" data-end="2465">buruk (negatif)</strong>, lebih baik kita buang dan mulai subarray baru dari <code data-start="2518" data-end="2521">x</code>.</p></li></ul> <div class="jump-break" data-jump-break="true"> <span class="jump-break__label"><br></span></div></div></li><li><h1>Pseudocode Kadane<br></h1><p>Asumsi panjang array ≥ 1.<br> </p><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>function maxSubArray(nums):<br> currentSum = nums[0]<br> maxSum = nums[0]<br><br> for i from 1 to n-1:<br> currentSum = max(nums[i], currentSum + nums[i])<br> maxSum = max(maxSum, currentSum)<br><br> return maxSum</code></pre> </div> <ul><li>Kompleksitas waktu: <strong data-start="2833" data-end="2841">O(n)</strong></li><li>Kompleksitas ruang: <strong data-start="2866" data-end="2874">O(1)</strong> (pakai beberapa variabel saja)</li></ul><h1> </h1><div class="jump-break" data-jump-break="true"> <span class="jump-break__label"><br></span> </div></li><li><h1>Contoh Penelusuran Langkah demi Langkah<br></h1><p data-start="2959" data-end="3005">Untuk <code data-start="2965" data-end="3005">nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]</code></p> <p data-start="3007" data-end="3012">Awal:</p><h1> </h1><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>currentSum = -2<br>maxSum = -2</code></pre> </div> <p>Indeks 1, nilai = 1</p><h1> </h1><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>currentSum = max(1, -2 + 1) = max(1, -1) = 1<br>maxSum = max(-2, 1) = 1</code></pre> </div> <p>Indeks 2, nilai = -3</p><h1> </h1><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>currentSum = max(-3, 1 + (-3)) = max(-3, -2) = -3<br>maxSum = max(1, -3) = 1</code></pre> </div> <p>Indeks 3, nilai = 4<br> </p><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>currentSum = max(4, -3 + 4) = max(4, 1) = 4<br>maxSum = max(1, 4) = 4</code></pre> </div> <p>Indeks 4, nilai = -1<br> </p><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>currentSum = max(-1, 4 + (-1)) = max(-1, 3) = 3<br>maxSum = max(4, 3) = 4</code></pre> </div> <p>Indeks 5, nilai = 2<br> </p><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>currentSum = max(2, 3 + 2) = max(2, 5) = 5<br>maxSum = max(4, 5) = 5</code></pre> </div> <p>Indeks 6, nilai = 1<br> </p><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>currentSum = max(1, 5 + 1) = 6<br>maxSum = max(5, 6) = 6</code></pre> </div> <p>Indeks 7, nilai = -5<br> </p><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>currentSum = max(-5, 6 + (-5)) = max(-5, 1) = 1<br>maxSum = max(6, 1) = 6</code></pre> </div> <p>Indeks 8, nilai = 4</p><h1> </h1><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>currentSum = max(4, 1 + 4) = 5<br>maxSum = max(6, 5) = 6</code></pre> </div> <p>Hasil: <code data-start="3891" data-end="3903">maxSum = 6</code> (subarray <code data-start="3914" data-end="3929">[4, -1, 2, 1]</code>).</p><div class="jump-break" data-jump-break="true"> <span class="jump-break__label"><br></span> </div></li><li><h1>Implementasi di Berbagai Bahasa<br></h1><p>Semua contoh di bawah mengembalikan <strong data-start="4013" data-end="4024">max sum</strong> saja.<br></p><p data-start="3977" data-end="4145">Asumsi: array tidak kosong. Kalau mau aman, bisa tambah pengecekan <code data-start="4100" data-end="4116">if length == 0</code> → throw error atau return 0.</p></li><ol><li><h1>Java<br> </h1><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>public class KadaneMaxSubarray {<br><br> // Mengembalikan jumlah maksimum subarray kontigu<br> public static int maxSubArray(int[] nums) {<br> if (nums == null || nums.length == 0) {<br> throw new IllegalArgumentException("Array tidak boleh null atau kosong");<br> }<br><br> int currentSum = nums[0];<br> int maxSum = nums[0];<br><br> for (int i = 1; i < nums.length; i++) {<br> // Pilih: lanjutkan subarray sebelumnya atau mulai baru dari nums[i]<br> currentSum = Math.max(nums[i], currentSum + nums[i]);<br> // Update nilai maksimum global<br> maxSum = Math.max(maxSum, currentSum);<br> }<br><br> return maxSum;<br> }<br><br> public static void main(String[] args) {<br> int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};<br> int result = maxSubArray(nums);<br> System.out.println("Max subarray sum = " + result); // Output: 6<br> }<br>}</code></pre> </div></li><li><h1>C<br> </h1><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>#include <stdio.h><br>#include <limits.h><br><br>int maxSubArray(int nums[], int n) {<br> if (n == 0) {<br> // Terserah kebutuhan: bisa return 0 atau error<br> return 0;<br> }<br><br> int currentSum = nums[0];<br> int maxSum = nums[0];<br><br> for (int i = 1; i < n; i++) {<br> // currentSum = max(nums[i], currentSum + nums[i])<br> if (currentSum + nums[i] > nums[i]) {<br> currentSum = currentSum + nums[i];<br> } else {<br> currentSum = nums[i];<br> }<br><br> // maxSum = max(maxSum, currentSum)<br> if (currentSum > maxSum) {<br> maxSum = currentSum;<br> }<br> }<br><br> return maxSum;<br>}<br><br>int main() {<br> int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};<br> int n = sizeof(nums) / sizeof(nums[0]);<br> int result = maxSubArray(nums, n);<br> printf("Max subarray sum = %d\n", result); // Output: 6<br> return 0;<br>}</code></pre> </div></li><li><h1>Python<br> </h1><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>def max_sub_array(nums):<br> if not nums:<br> raise ValueError("List tidak boleh kosong")<br><br> current_sum = nums[0]<br> max_sum = nums[0]<br><br> for i in range(1, len(nums)):<br> # current_sum = max(nums[i], current_sum + nums[i])<br> current_sum = max(nums[i], current_sum + nums[i])<br> # max_sum = max(max_sum, current_sum)<br> max_sum = max(max_sum, current_sum)<br><br> return max_sum<br><br><br>if __name__ == "__main__":<br> nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]<br> result = max_sub_array(nums)<br> print("Max subarray sum =", result) # Output: 6</code></pre> </div></li><li><h1>Go (Golang)<br> </h1><div class="code-box"> <div class="code-box__header"> <span class="code-box__title">Code</span> <button type="button" class="code-box__copy" data-copy-code="">Copy code</button> </div> <pre><code>package main<br><br>import (<br> "fmt"<br>)<br><br>func maxSubArray(nums []int) int {<br> if len(nums) == 0 {<br> panic("slice tidak boleh kosong")<br> }<br><br> currentSum := nums[0]<br> maxSum := nums[0]<br><br> for i := 1; i < len(nums); i++ {<br> // currentSum = max(nums[i], currentSum + nums[i])<br> if currentSum+nums[i] > nums[i] {<br> currentSum = currentSum + nums[i]<br> } else {<br> currentSum = nums[i]<br> }<br><br> // maxSum = max(maxSum, currentSum)<br> if currentSum > maxSum {<br> maxSum = currentSum<br> }<br> }<br><br> return maxSum<br>}<br><br>func main() {<br> nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}<br> result := maxSubArray(nums)<br> fmt.Println("Max subarray sum =", result) // Output: 6<br>}</code></pre> </div></li><li><h1>AA</h1></li></ol></ol><h1> </h1><div class="jump-break" data-jump-break="true"> <span class="jump-break__label"><br></span> </div><ol><li><h1><br></h1></li><li><h1><br></h1></li><li><h1><br></h1></li><li><h1><br></h1></li><li><h1><br></h1></li><li><h1>AA</h1></li><li><br></li><li><h1>AA</h1></li></ol><br>