Algoritma Kadane

Kadane's Algorithm adalah algoritma terbaik untuk menemukan subarray yang memiliki jumlah maksimum di antara semua subarray.

arr[]={-5, 4,  6, -3 , 4, -1}

Dalam array ini, subarray {4, 6, -3 , 4 } memiliki jumlah maksimum.

Pendekatan Paling Sederhana untuk menyelesaikan masalah ini adalah menghitung jumlah semua subarray, lalu mencetak subarray dengan jumlah maksimum. Namun, karena cara ini memerlukan dua iterasi, kompleksitas waktunya menjadi n² . 

Dengan menggunakan Kadane's Algorithm, kompleksitas waktu berkurang drastis.

Pendekatan

Jika elemen subarray bernilai positif, kita dapat menambahkannya ke jumlah. 

Oleh karena itu, jika jumlah kumulatif subarray mana pun menjadi negatif, abaikan bagian tersebut. 

Mulai dari awal dan tambahkan elemen-elemennya, lalu simpan nilai maksimum dari jumlah kumulatif. Jika jumlahnya menjadi negatif, hapus bagian tersebut dan mulai lagi dari indeks berikutnya.

1. Buat dua variabel bernama maxSum dan cumSum, lalu tetapkan nilai keduanya menjadi 0.

2. Jalankan perulangan dari 0 hingga n kali.

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
  
}

3. Hitung jumlah kumulatif subarray seperti berikut.

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
}

4. Jika cumSum lebih besar daripada maxSum, simpan nilainya di maxSum.

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
   
   if(cumSum>maxSum){
      maxSum=cumSum;
   }
}

5. Seperti yang telah kita bahas, jika jumlah kumulatif menjadi negatif, abaikan nilai tersebut. Jumlah maksimum yang dapat dihasilkan sudah tersimpan dalam variabel maxSum. Jadi, jika  cumSum menjadi negatif, ubah nilainya kembali menjadi 0 dan mulai lagi dari indeks berikutnya seperti berikut.

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
   
   if(cumSum>maxSum){
      maxSum=cumSum;
   }
   
   if(cumSum<0){
      cumSum=0;
   }
}

6. Setelah mengiterasi seluruh array, jumlah maksimum tersimpan dalam variabel maxSum.

Ingat, jika jumlah maksimum subarray bernilai negatif, kita harus menyesuaikan fungsi tersebut. Coba lakukan sendiri.

Analisis Kompleksitas Waktu

Karena kita hanya mengiterasi array satu kali, kompleksitas waktunya adalah O(n). Ini merupakan peningkatan yang signifikan dibandingkan pendekatan sebelumnya.

Untuk mengetahui lebih lanjut tentang Kadane's Algorithm

Kadane's Algorithm