Alambiyah Studio
Artikel

Array – Subarray Max Sum (Kadane’s Algorithm)

Array – Subarray Max Sum (Kadane’s Algorithm) Input: array integer Tugas: cari jumlah subarray kontigu dengan total terbesar.

28 Nov 2025 Tim Alambiyah

  1. Rumusan Soal

    Diberikan sebuah array integer nums berukuran n (bisa berisi bilangan positif, nol, dan negatif). Cari subarray kontigu (elemen berurutan, tidak boleh lompat) yang memiliki jumlah (sum) terbesar, lalu kembalikan nilai jumlahnya.
    Contoh:

    Code 
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

    Subarray dengan jumlah terbesar: [4, -1, 2, 1]
    Jumlah = 4 + (-1) + 2 + 1 = 6

    Output: 6

    Catatan penting:

    • Yang dicari adalah subarray (kontigu), bukan subset (boleh lompat).
    • Jika semua elemen negatif, kita tetap pilih satu elemen terbesar (misalnya [-5, -2, -7] ➙ -2)

  2. Cara Paling Naif (Brute Force) - Sekilas

    Pendekatan awal (untuk memahami konsep):

    1. Ambil semua pasangan indeks i (sebagai awal) dan j (sebagai akhir).
    2. Hituing jumlah elemen dario i sampai j.
    3. Simpan nilai maksimum selama perulangan.

    Pseudocode ide dasarnya:

    Code 
    maxSum = -∞
    for i from 0 to n-1:
        for j from i to n-1:
            sum = 0
            for k from i to j:
                sum += nums[k]
            maxSum = max(maxSum, sum)
    return maxSum
    • Kompleksitas waktu: O(n³) (karena tiga loop).
    • Bisa dioptimasi dengan prefix sum jadi O(n²), tapi masih lambat untuk n besar.
    Karena itu kita butuh cara yang O(n) → di sinilah Kadane’s Algorithm dipakai.

  3. Intuisi Kadane's Algorithm

    Idenya sederhana:

    Kalau sum sementara yang kita punya sudah negatif, menambahkannya ke elemen berikutnya itu tidak akan membantu — malah membuat jumlah jadi lebih kecil.
    Jadi, kalau sudah negatif, reset saja di elemen berikutnya.

    Kita jalan dari kiri ke kanan sambil menjaga dua nilai:

    1. currentSum = jumlah subarray berakhir di indeks saat ini

    2. maxSum = jumlah subarray terbesar yang pernah kita temukan sejauh ini

    Setiap melihat nilaix = nums[i]:
    • Ada dua pilihan:
      • Lanjutkan subarray sebelumnya: currentSum + x
      • Mulai subarray baru dari x saja
    Kita pilih yang lebih besar:
    Code 
    currentSum = max(x, currentSum + x)
    maxSum = max(maxSum, currentSum)

    Kenapa begitu?

    • Jika currentSum + x lebih besar → subarray terbaik yang berakhir di i adalah dengan melanjutkan sebelumnya.

    • Jika x lebih besar → berarti currentSum sebelumnya buruk (negatif), lebih baik kita buang dan mulai subarray baru dari x.


  4. Pseudocode Kadane

    Asumsi panjang array ≥ 1.

    Code 
    function maxSubArray(nums):
        currentSum = nums[0]
        maxSum = nums[0]

        for i from 1 to n-1:
            currentSum = max(nums[i], currentSum + nums[i])
            maxSum = max(maxSum, currentSum)

        return maxSum
    • Kompleksitas waktu: O(n)
    • Kompleksitas ruang: O(1) (pakai beberapa variabel saja)

  5. Contoh Penelusuran Langkah demi Langkah

    Untuk nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

    Awal:

    Code 
    currentSum = -2
    maxSum     = -2

    Indeks 1, nilai = 1

    Code 
    currentSum = max(1, -2 + 1) = max(1, -1) = 1
    maxSum     = max(-2, 1) = 1

    Indeks 2, nilai = -3

    Code 
    currentSum = max(-3, 1 + (-3)) = max(-3, -2) = -3
    maxSum     = max(1, -3) = 1

    Indeks 3, nilai = 4

    Code 
    currentSum = max(4, -3 + 4) = max(4, 1) = 4
    maxSum     = max(1, 4) = 4

    Indeks 4, nilai = -1

    Code 
    currentSum = max(-1, 4 + (-1)) = max(-1, 3) = 3
    maxSum     = max(4, 3) = 4

    Indeks 5, nilai = 2

    Code 
    currentSum = max(2, 3 + 2) = max(2, 5) = 5
    maxSum     = max(4, 5) = 5

    Indeks 6, nilai = 1

    Code 
    currentSum = max(1, 5 + 1) = 6
    maxSum     = max(5, 6) = 6

    Indeks 7, nilai = -5

    Code 
    currentSum = max(-5, 6 + (-5)) = max(-5, 1) = 1
    maxSum     = max(6, 1) = 6

    Indeks 8, nilai = 4

    Code 
    currentSum = max(4, 1 + 4) = 5
    maxSum     = max(6, 5) = 6

    Hasil: maxSum = 6 (subarray [4, -1, 2, 1]).

  6. Implementasi di Berbagai Bahasa

    Semua contoh di bawah mengembalikan max sum saja.

    Asumsi: array tidak kosong. Kalau mau aman, bisa tambah pengecekan if length == 0 → throw error atau return 0.

    1. Java

      Code 
      public class KadaneMaxSubarray {

          // Mengembalikan jumlah maksimum subarray kontigu
          public static int maxSubArray(int[] nums) {
              if (nums == null || nums.length == 0) {
                  throw new IllegalArgumentException("Array tidak boleh null atau kosong");
              }

              int currentSum = nums[0];
              int maxSum = nums[0];

              for (int i = 1; i < nums.length; i++) {
                  // Pilih: lanjutkan subarray sebelumnya atau mulai baru dari nums[i]
                  currentSum = Math.max(nums[i], currentSum + nums[i]);
                  // Update nilai maksimum global
                  maxSum = Math.max(maxSum, currentSum);
              }

              return maxSum;
          }

          public static void main(String[] args) {
              int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
              int result = maxSubArray(nums);
              System.out.println("Max subarray sum = " + result); // Output: 6
          }
      }

    2. C

      Code 
      #include <stdio.h>
      #include <limits.h>

      int maxSubArray(int nums[], int n) {
          if (n == 0) {
              // Terserah kebutuhan: bisa return 0 atau error
              return 0;
          }

          int currentSum = nums[0];
          int maxSum = nums[0];

          for (int i = 1; i < n; i++) {
              // currentSum = max(nums[i], currentSum + nums[i])
              if (currentSum + nums[i] > nums[i]) {
                  currentSum = currentSum + nums[i];
              } else {
                  currentSum = nums[i];
              }

              // maxSum = max(maxSum, currentSum)
              if (currentSum > maxSum) {
                  maxSum = currentSum;
              }
          }

          return maxSum;
      }

      int main() {
          int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
          int n = sizeof(nums) / sizeof(nums[0]);
          int result = maxSubArray(nums, n);
          printf("Max subarray sum = %d\n", result); // Output: 6
          return 0;
      }

    3. Python

      Code 
      def max_sub_array(nums):
          if not nums:
              raise ValueError("List tidak boleh kosong")

          current_sum = nums[0]
          max_sum = nums[0]

          for i in range(1, len(nums)):
              # current_sum = max(nums[i], current_sum + nums[i])
              current_sum = max(nums[i], current_sum + nums[i])
              # max_sum = max(max_sum, current_sum)
              max_sum = max(max_sum, current_sum)

          return max_sum


      if __name__ == "__main__":
          nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
          result = max_sub_array(nums)
          print("Max subarray sum =", result)  # Output: 6

    4. Go (Golang)

      Code 
      package main

      import (
      	"fmt"
      )

      func maxSubArray(nums []int) int {
      	if len(nums) == 0 {
      		panic("slice tidak boleh kosong")
      	}

      	currentSum := nums[0]
      	maxSum := nums[0]

      	for i := 1; i < len(nums); i++ {
      		// currentSum = max(nums[i], currentSum + nums[i])
      		if currentSum+nums[i] > nums[i] {
      			currentSum = currentSum + nums[i]
      		} else {
      			currentSum = nums[i]
      		}

      		// maxSum = max(maxSum, currentSum)
      		if currentSum > maxSum {
      			maxSum = currentSum
      		}
      	}

      	return maxSum
      }

      func main() {
      	nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
      	result := maxSubArray(nums)
      	fmt.Println("Max subarray sum =", result) // Output: 6
      }

    5. AA






  6. AA


  8. AA


Kembali ke blog