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)
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.
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.

Pseudocode Kadane

Asumsi panjang array ≥ 1.

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)

Contoh Penelusuran Langkah demi Langkah

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

Awal:

currentSum = -2
maxSum     = -2

Indeks 1, nilai = 1

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

Indeks 2, nilai = -3

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

Indeks 3, nilai = 4

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

Indeks 4, nilai = -1

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

Indeks 5, nilai = 2

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

Indeks 6, nilai = 1

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

Indeks 7, nilai = -5

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

Indeks 8, nilai = 4

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

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

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.

Java

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
    }
}

C

#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;
}

Python

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

Go (Golang)

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
}

AA

AA
AA

Insight seputar website, event, dan konten

Array – Subarray Max Sum (Kadane’s Algorithm)