Masalah Sub-Array Maksimum sama dengan Masalah Slice Maksimum. Tutorial ini membahas masalah dengan coding di C++. Pertanyaannya adalah: berapa jumlah maksimum dari setiap kemungkinan urutan angka berurutan dalam sebuah array? Ini bisa berarti seluruh array. Masalah ini dan solusinya dalam bahasa apapun, disebut sebagai Masalah Sub-Array Maksimum. Array dapat memiliki kemungkinan angka negatif.
Solusinya harus efisien. Itu perlu memiliki kompleksitas waktu tercepat. Sampai sekarang, algoritma tercepat untuk solusi ini dikenal di komunitas ilmiah sebagai Algoritma Kadane. Artikel ini menjelaskan algoritma Kadane dengan C++.
Contoh Data
Perhatikan vektor berikut (array):
vektor < ke dalam > A = { 5 , - 7 , 3 , 5 , - dua , 4 , - 1 } ;
Irisan (sub-array) dengan jumlah maksimum adalah urutan, {3, 5, -2, 4}, yang memberikan jumlah 10. Tidak ada urutan lain yang mungkin, bahkan seluruh array, akan memberikan jumlah hingga nilai 10. Seluruh array memberikan jumlah 7, yang bukan jumlah maksimum.
Perhatikan vektor berikut:
vektor < ke dalam > B = { - dua , 1 , - 3 , 4 , - 1 , dua , 1 , - 5 , 4 } ;
Irisan (sub-array) dengan jumlah maksimum adalah barisan, {4, 1, 2, 1} yang menghasilkan jumlah 6. Perhatikan bahwa dapat ada bilangan negatif di dalam sub-array untuk jumlah maksimum.
Perhatikan vektor berikut:
vektor < ke dalam > C = { 3 , dua , - 6 , 4 , 0 } ;
Irisan (sub-array) dengan jumlah maksimum adalah urutan, {3, 2} yang memberikan jumlah 5.
Perhatikan vektor berikut:
vektor < ke dalam > D = { 3 , dua , 6 , - 1 , 4 , 5 , - 1 , dua } ;
Sub-array dengan jumlah maksimum adalah barisan, {3, 2, 6, -1, 4, 5, -1, 2} yang menghasilkan jumlah 20. Ini adalah seluruh array.
Perhatikan vektor berikut:
vektor < ke dalam > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , limabelas , 4 , - 8 , - limabelas , - 22 } ;
Ada dua sub-array dengan jumlah maksimum, di sini. Jumlah yang lebih tinggi adalah yang dianggap sebagai solusi (jawaban) untuk masalah sub-array maksimum. Sub-arraynya adalah: {5, 7} dengan jumlah 12, dan {6, 5, 10, -5, 15, 4} dengan jumlah 35. Tentu saja, irisan dengan jumlah 35, adalah jawabannya.
Perhatikan vektor berikut:
vektor < ke dalam > F = { - 4 , 10 , limabelas , 9 , - 5 , - dua puluh , - 3 , - 12 , - 3 , 4 , 6 , 3 , dua , 8 , 3 , - 5 , - dua } ;
Ada dua sub-array dengan jumlah maksimum. Jumlah yang lebih tinggi adalah yang dianggap sebagai solusi untuk masalah sub-array maksimum. Sub-arraynya adalah: {10, 15, 9} dengan jumlah 34, dan {4, 6, 3, 2, 8, 3} dengan jumlah 26. Tentu saja, irisan dengan jumlah 34 adalah jawabannya karena masalahnya adalah mencari sub-array dengan jumlah tertinggi dan bukan sub-array dengan jumlah yang lebih tinggi.
Mengembangkan Algoritma Kadane
Informasi di bagian tutorial ini bukan karya asli dari Kadane. Ini adalah cara penulis sendiri untuk mengajarkan algoritma Kadane. Salah satu vektor di atas, dengan total berjalannya, ada di tabel ini:
| Data | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | limabelas | 4 | -8 | -limabelas | -22 |
| Total Berjalan | 5 | 12 | 8 | -dua | -8 | -dua | 3 | 13 | 8 | 23 | 27 | dua puluh satu | 16 | -6 |
| indeks | 0 | 1 | dua | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | sebelas | 12 | 13 |
Running Total untuk indeks adalah jumlah dari semua nilai sebelumnya termasuk untuk indeks. Ada dua urutan dengan jumlah maksimum di sini. Mereka adalah {5, 7}, yang memberikan jumlah 12, dan {6, 5, 10, -5, 15, 4}, yang memberikan jumlah 35. Urutan yang memberikan jumlah 35 adalah yang diinginkan .
Perhatikan bahwa untuk total yang berjalan, ada dua puncak yang merupakan nilai, 12 dan 27. Puncak ini sesuai dengan indeks terakhir dari dua urutan.
Jadi, ide dari algoritma Kadane adalah melakukan total berjalan sambil membandingkan jumlah maksimum yang ditemui, bergerak dari kiri ke kanan dalam larik yang diberikan.
Vektor lain dari atas, dengan total berjalannya, ada di tabel ini:
Ada dua barisan dengan jumlah maksimum. Mereka adalah {10, 15, 9}, yang memberikan jumlah 34; dan {4, 6, 3, 2, 8, 3} yang memberikan jumlah 26. Urutan yang memberikan jumlah 34, adalah apa yang diinginkan.
Perhatikan bahwa untuk total berjalan, ada dua puncak yang merupakan nilai, 30 dan 13. Puncak ini sesuai dengan indeks terakhir dari dua urutan.
Sekali lagi, ide dari algoritma Kadane adalah melakukan total berjalan sambil membandingkan jumlah maksimum yang ditemui, bergerak dari kiri ke kanan dalam larik yang diberikan.
Kode dengan Algoritma Kadane di C++
Kode yang diberikan di bagian artikel ini belum tentu digunakan oleh Kadane. Namun, itu dengan algoritmanya. Program seperti banyak program C++ lainnya, akan dimulai dengan:
#sertakan#sertakan
menggunakan namespace std;
Ada penyertaan perpustakaan iostream, yang bertanggung jawab untuk input dan output. Ruang nama standar digunakan.
Ide dari algoritma Kadane adalah memiliki total berjalan sambil membandingkan jumlah maksimum yang ditemui, bergerak dari kiri ke kanan dalam array yang diberikan. Fungsi dari algoritma tersebut adalah:
int maxSunArray ( vektor < ke dalam > & SEBUAH ) {int N = A.ukuran ( ) ;
int maxJumlah = A [ 0 ] ;
int runJumlah = A [ 0 ] ;
untuk ( ke dalam saya = 1 ; saya < N; saya++ ) {
int tempRunTotal = runTotal + A [ saya ] ; // bisa lebih kecil dari A [ saya ]
jika ( SEBUAH [ saya ] > tempRunTotal )
runTotal = A [ saya ] ; // di kasus SEBUAH [ saya ] lebih besar dari total lari
kalau tidak
runTotal = tempRunTotal;
jika ( menjalankanTotal > jumlah maks ) // membandingkan semua jumlah maksimum
maxSum = jumlah total;
}
kembali jumlah maks;
}
Ukuran, N dari array yang diberikan (vektor) ditentukan. Variabel, maxSum adalah salah satu jumlah maksimum yang mungkin. Sebuah array memiliki setidaknya satu jumlah maksimum. Variabel, runTotal mewakili total berjalan di setiap indeks. Keduanya diinisialisasi dengan nilai pertama dari array. Dalam algoritma ini, jika nilai berikutnya dalam array lebih besar dari total berjalan maka nilai berikutnya akan menjadi total berjalan baru.
Ada satu for-loop utama. Pemindaian dimulai dari 1 dan bukan nol karena inisialisasi variabel, maxSum dan runTotal ke A[0] yang merupakan elemen pertama dari array yang diberikan.
Dalam for-loop, pernyataan pertama menentukan total running sementara dengan menambahkan nilai saat ini ke jumlah akumulasi dari semua nilai sebelumnya.
Selanjutnya, ada konstruk if/else. Jika nilai saat ini saja lebih besar dari total berjalan sejauh ini, maka nilai tunggal itu menjadi total berjalan. Ini berguna terutama jika semua nilai dalam larik yang diberikan adalah negatif. Dalam hal ini, nilai negatif tertinggi saja akan menjadi nilai maksimum (jawabannya). Jika nilai saat ini saja tidak lebih besar dari total berjalan sementara sejauh ini, maka total berjalan menjadi total berjalan sebelumnya ditambah nilai saat ini, – ini adalah bagian lain dari konstruksi if/else.
Segmen kode terakhir di for-loop memilih antara jumlah maksimum sebelumnya untuk urutan sebelumnya (sub-array) dan jumlah maksimum saat ini untuk urutan saat ini. Oleh karena itu, nilai yang lebih tinggi dipilih. Bisa ada lebih dari satu jumlah sub-array maksimum. Perhatikan bahwa total yang berjalan akan naik dan turun, karena larik dipindai dari kiri ke kanan. Itu jatuh karena memenuhi nilai negatif.
Jumlah sub-array maksimum yang dipilih terakhir dikembalikan setelah for-loop.
Konten untuk fungsi utama C++ yang sesuai, untuk fungsi algoritma Kadane adalah:
vektor < ke dalam > A = { 5 , - 7 , 3 , 5 , - dua , 4 , - 1 } ; // { 3 , 5 , - dua , 4 } - > 10int ret1 = maxSunArray ( SEBUAH ) ;
cout << ret1 << akhir;
vektor < ke dalam > B = { - dua , 1 , - 3 , 4 , - 1 , dua , 1 , - 5 , 4 } ; // { 4 , 1 , dua , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << akhir;
vektor < ke dalam > C = { 3 , dua , - 6 , 4 , 0 } ; // { 3 , dua } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << akhir;
vektor < ke dalam > D = { 3 , dua , 6 , - 1 , 4 , 5 , - 1 , dua } ; // { 3 , dua , 6 , - 1 , 4 , 5 , - 1 , dua } - > 5
int ret4 = maxSunArray ( D ) ;
cout << bersih4 << akhir;
vektor < ke dalam > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , limabelas , 4 , - 8 , - limabelas , - 22 } ; // { 6 , 5 , 10 , - 5 , limabelas , 4 } - > 35
int ret5 = maxSunArray ( DAN ) ;
cout << ret5 << akhir;
vektor < ke dalam > F = { - 4 , 10 , limabelas , 9 , - 5 , - dua puluh , - 3 , - 12 , - 3 , 4 , 6 , 3 , dua , 8 , 3 , - 5 , - dua } ; // { 10 , limabelas , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << benar 6 << akhir;
Dengan itu, outputnya akan menjadi:
10
6
5
dua puluh
35
3. 4
Setiap jawaban baris di sini, sesuai dengan array yang diberikan, secara berurutan.
Kesimpulan
Kompleksitas waktu untuk algoritma Kadane adalah O(n), di mana n adalah jumlah elemen dalam array yang diberikan. Kompleksitas waktu ini adalah yang tercepat untuk masalah sub-array maksimum. Ada algoritma lain yang lebih lambat. Ide dari algoritma Kadane adalah melakukan total berjalan, sambil membandingkan jumlah maksimum yang ditemui, bergerak dari kiri ke kanan dalam larik yang diberikan. Jika nilai saat ini saja lebih besar dari total lari sejauh ini, maka nilai tunggal itu menjadi total lari baru. Jika tidak, total berjalan baru adalah total berjalan sebelumnya ditambah elemen saat ini, seperti yang diantisipasi, karena larik yang diberikan dipindai.
Mungkin ada lebih dari satu jumlah maksimum, untuk kemungkinan sub-array yang berbeda. Jumlah maksimum tertinggi, untuk semua kemungkinan sub-array, dipilih.
Apa indeks pembatas untuk kisaran jumlah maksimum yang dipilih? – Itu adalah diskusi untuk lain waktu!
Chrys