Algoritma Kadence: Subarray Bersebelahan Jumlah Terbesar

Berapakah Jumlah Subarray Berurutan Terbesar?

Subarray adalah bagian kontinu dari sebuah array. Ini bisa berupa elemen tunggal dari array atau sebagian kecil dari array. Subarray bersebelahan dengan jumlah terbesar berarti subarray yang memiliki nilai jumlah maksimum.

Sebagai contoh, perhatikan larik {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Sub-lariknya bisa berupa {-10, 5, 1, 6}, {5, 1, 6}, atau {2, -7, 3, -5}, dan seterusnya. Namun, {5, 1, 6, 3} tidak dapat menjadi sub-larik karena elemen-elemennya tidak berurutan.

Jika Anda perhatikan, di antara semua sub-array, sub-array yang disorot {5, 1, 6} memiliki nilai penjumlahan maksimum:

Jumlah sub-array {5, 1, 6} adalah 12, jumlah maksimum di antara semua kemungkinan sub-array dari array di atas. Jadi, untuk array ini, sub-array berurutan dengan jumlah maksimum adalah {5, 1, 6}.

Pendekatan Sederhana untuk Menyelesaikan Subarray Berurutan dengan Jumlah Terbesar

Cara sederhana untuk menyelesaikan masalah ini adalah dengan menggunakan dua loop untuk mencari semua subarray, menghitung jumlahnya, dan kemudian mencari nilai maksimumnya.

Berikut adalah diagram alir untuk pendekatan sederhana dalam menemukan sub-array berurutan dengan jumlah terbesar. Ini adalah pendekatan brute-force, karena kita menelusuri setiap sub-array yang mungkin.

Berikut langkah sederhana untuk melakukan ini.

Langkah 1) Inisialisasi jumlah_maksimum dengan nilai bilangan bulat minimum dan atur mulai ke akhir ke nol.

Langkah 2) membiarkan i ke j menjadi indeks array di mana j lebih besar atau sama dengan i; i menandai awal sub-array dan j akhirnya.

Langkah 3) jumlah_saat_ini menyimpan jumlah kumulatif. Setelah setiap pembaruan, periksa apakah jumlah_saat_ini lebih besar dari jumlah_maksimum.

Langkah 4) If jumlah_saat_ini lebih besar, ganti jumlah_maksimum dengan itu.

Langkah 5) Ketika j mencapai akhir array, tambah i dan atur ulang jumlah_saat_ini ke 0.

Langkah 6) Ulangi sampai i mencapai akhir array. jumlah_maksimum lalu menyimpan jumlah sub-array terbesar.

Pseudo Code untuk Pendekatan Sederhana

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum

C++ Penerapan Pendekatan Sederhana

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
    int max_sum = -1e9;
    int begin = 0;
    int end = 0;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += array[j];
            if (max_sum < current_sum) {
                max_sum = current_sum;
                begin = i;
                end = j;
            }
        }
    }
    cout << "largest sum is " << max_sum << endl;
    cout << "largest sum contiguous subarray: ";
    for (int i = begin; i <= end; i++) {
        cout << array[i] << "\t";
    }
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

Keluaran:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python Penerapan Pendekatan Sederhana

def maximumSubarraySum(numbers):
    max_sum, begin, end = -1e9, 0, 0
    for i in range(len(numbers)):
        current_sum = 0
        for j in range(i, len(numbers)):
            current_sum += numbers[j]
            if max_sum < current_sum:
                max_sum = current_sum
                begin, end = i, j
    print("largest sum is ", max_sum)
    print("largest sum contiguous subarray: ", end='')
    for i in range(begin, end + 1):
        print(numbers[i], end='\t')

numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5]
maximumSubarraySum(numbers)

Keluaran:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Algoritma Kadane untuk Menemukan Subarray Berurutan dengan Jumlah Terbesar

Algoritma Kadane adalah metode Pemrograman Dinamis yang menggunakan satu perulangan saja, bukan dua. Algoritma ini menangani array dengan campuran bilangan positif dan negatif, selama setidaknya satu nilainya bukan negatif.

Kita hanya membutuhkan dua variabel untuk menemukan sub-array berurutan dengan jumlah terbesar. Berikut adalah diagram alirnya:

Berikut langkah-langkah Algoritma Kadane :

Langkah 1) Buat dua variabel, jumlah_saat_ini ke jumlah_maksimum.

jumlah_saat_ini menyimpan jumlah maksimum yang berakhir pada indeks array tertentu, sementara jumlah_maksimum menyimpan nilai penjumlahan terbesar yang diamati sejauh ini.

Langkah 2) Tambahkan setiap elemen array ke jumlah_saat_iniKemudian periksa dua kondisi di bawah ini:

• If jumlah_saat_ini jika kurang dari elemen saat ini, maka jumlah_saat_ini menjadi elemen saat ini.
• If jumlah_maksimum kurang dari jumlah_saat_ini, kemudian jumlah_maksimum menjadi jumlah_saat_ini.

Langkah 3) Setelah mengulangi langkah sebelumnya untuk seluruh array, jumlah_maksimum berisi sub-array berurutan dengan jumlah terbesar.

Contoh Algoritma Kadane

Kami mendemonstrasikan Algoritma Kadane pada array kecil dan menjelaskan setiap langkah dalam menemukan sub-array berurutan dengan jumlah terbesar.

Mari kita asumsikan array yang diberikan adalah sebagai berikut:

Berikut adalah langkah-langkah Algoritma Kadane:

Langkah 1) Buat dua variabel, jumlah_saat_ini ke jumlah_maksimumTetapkan INT_MIN ke jumlah_maksimum dan nol hingga jumlah_saat_iniDi sini, INT_MIN mewakili nilai bilangan bulat minimum.

Langkah 2) Pada indeks 0, nilainya adalah 4. Jadi, jumlah_saat_ini = 0 + 4 = 4. Karena jumlah_saat_ini lebih besar dari jumlah_maksimum, jumlah_maksimum menjadi 4.

Langkah 3) Pada indeks 1, nilainya adalah -2. Jadi, jumlah_saat_ini = 4 + (-2) = 2.

Kali ini jumlah_saat_ini kurang dari jumlah_maksimumAkibatnya, nilai dari jumlah_maksimum belum diperbarui.

Langkah 4) Nilai selanjutnya adalah 1. Menambahkannya ke jumlah_saat_ini memberikan 3. Karena jumlah_maksimum (4) masih lebih besar dari jumlah_saat_ini, jumlah_maksimum belum diperbarui.

Langkah 5) Pada indeks 3, nilainya adalah 3. Peningkatan jumlah_saat_ini dengan 3 memberikan jumlah_saat_ini = 6.

Di sini: jumlah_maksimum lebih kecil dari jumlah_saat_ini, sehingga jumlah_maksimum diperbarui dengan nilai jumlah_saat_ini.

Langkah 6) Untuk elemen terakhir dari array, kita memiliki -1. Menambahkannya ke jumlah_saat_ini memberikan 5, yang lebih kecil dari jumlah_maksimum. Begitu, jumlah_maksimum tersisa 6.

Karena kita telah mencapai akhir array, algoritma berakhir di sini. Sekarang, jumlah_maksimum berisi jumlah maksimum, yaitu 6. Sub-arraynya adalah {4, -2, 1, 3}.

Pseudo Code untuk Algoritma Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++ Implementasi Algoritma Kadane

#include <iostream>
using namespace std;
void kadane(int array[], int n) {
    int current_sum = 0;
    int max_sum = -1e9;
    // -1e9 means -1,000,000,000
    for (int i = 0; i < n; i++) {
        current_sum += array[i];
        if (max_sum < current_sum) {
            max_sum = current_sum;
        }
        if (current_sum < array[i]) {
            current_sum = array[i];
        }
    }
    cout << "largest sum is " << max_sum << endl;
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    kadane(array, sizeof(array) / sizeof(array[0]));
}

Keluaran:

largest sum is 12

Python Implementasi Algoritma Kadane

def kadane(numbers):
    current_sum = 0
    max_sum = -1e9
    for i in range(len(numbers)):
        current_sum += numbers[i]
        if max_sum < current_sum:
            max_sum = current_sum
        if current_sum < numbers[i]:
            current_sum = numbers[i]
    print("largest sum is ", max_sum)

kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])

Keluaran:

largest sum is 12

Analisis Kompleksitas untuk Subarray Bersebelahan dengan Jumlah Terbesar

Pendekatan sederhana menggunakan dua loop untuk menghitung setiap kemungkinan jumlah sub-array dan menemukan yang terbesar. Ini adalah pendekatan brute-force; setiap loop berjalan hingga akhir array. susunan, memberi O(N²) waktu.

Algoritma Kadane hanya menggunakan satu loop, memberikan waktu O(N) dan ruang tambahan O(1). Pada array dengan 100 elemen, pendekatan sederhana melakukan 100 × 100 = 10,000 operasi, sedangkan algoritma Kadane hanya melakukan 100 operasi — peningkatan kecepatan yang dramatis untuk input yang besar.

Pertanyaan Umum Demo Slot