Masalah Sub-Array Maksimum adalah sama dengan Masalah Slice Maksimum. Tutorial ini membincangkan masalah dengan pengekodan dalam C++. Persoalannya ialah: apakah jumlah maksimum bagi sebarang urutan nombor berturut-turut yang mungkin dalam tatasusunan? Ini boleh bermakna keseluruhan tatasusunan. Masalah ini dan penyelesaiannya dalam mana-mana bahasa, dirujuk sebagai Masalah Sub-Array Maksimum. Tatasusunan boleh mempunyai nombor negatif yang mungkin.
Penyelesaiannya mestilah cekap. Ia perlu mempunyai kerumitan masa terpantas. Sehingga kini, algoritma terpantas untuk penyelesaian itu dikenali dalam komuniti saintifik sebagai Algoritma Kadane. Artikel ini menerangkan algoritma Kadane dengan C++.
Contoh Data
Pertimbangkan vektor berikut (tatasusunan):
vektor < int > A = { 5 , - 7 , 3 , 5 , - dua , 4 , - 1 } ;
Potongan (sub-array) dengan jumlah maksimum ialah jujukan, {3, 5, -2, 4}, yang memberikan jumlah 10. Tiada jujukan lain yang mungkin, malah keseluruhan tatasusunan, akan memberikan jumlah sehingga nilai 10. Seluruh tatasusunan memberikan jumlah 7, yang bukan jumlah maksimum.
Pertimbangkan vektor berikut:
vektor < int > B = { - dua , 1 , - 3 , 4 , - 1 , dua , 1 , - 5 , 4 } ;
Potongan (sub-array) dengan jumlah maksimum ialah jujukan, {4, −1, 2, 1} yang memberikan hasil tambah 6. Perhatikan bahawa mungkin terdapat nombor negatif dalam sub-array untuk jumlah maksimum.
Pertimbangkan vektor berikut:
vektor < int > C = { 3 , dua , - 6 , 4 , 0 } ;
Potongan (sub-array) dengan jumlah maksimum ialah jujukan, {3, 2} yang memberikan jumlah 5.
Pertimbangkan vektor berikut:
vektor < int > D = { 3 , dua , 6 , - 1 , 4 , 5 , - 1 , dua } ;
Sub-array dengan jumlah maksimum ialah jujukan, {3, 2, 6, -1, 4, 5, -1, 2} yang memberikan jumlah 20. Ia adalah keseluruhan tatasusunan.
Pertimbangkan vektor berikut:
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , lima belas , 4 , - 8 , - lima belas , - 22 } ;
Terdapat dua sub-tatasusunan dengan jumlah maksimum, di sini. Jumlah yang lebih tinggi adalah yang dianggap sebagai penyelesaian (jawapan) untuk masalah sub-array maksimum. Sub-tatasusunan ialah: {5, 7} dengan jumlah 12, dan {6, 5, 10, -5, 15, 4} dengan jumlah 35. Sudah tentu, kepingan dengan jumlah 35, ialah jawapan.
Pertimbangkan vektor berikut:
vektor < int > F = { - 4 , 10 , lima belas , 9 , - 5 , - dua puluh , - 3 , - 12 , - 3 , 4 , 6 , 3 , dua , 8 , 3 , - 5 , - dua } ;
Terdapat dua sub-tatasusunan dengan jumlah maksimum. Jumlah yang lebih tinggi adalah yang dianggap sebagai penyelesaian untuk masalah sub-array maksimum. Sub-tatasusunan ialah: {10, 15, 9} dengan jumlah 34, dan {4, 6, 3, 2, 8, 3} dengan jumlah 26. Sudah tentu, kepingan dengan jumlah 34 ialah jawapannya kerana masalahnya adalah untuk mencari sub-array dengan jumlah tertinggi dan bukan sub-array dengan jumlah yang lebih tinggi.
Membangunkan Algoritma Kadane
Maklumat dalam bahagian tutorial ini bukanlah karya asal daripada Kadane. Ia adalah cara pengarang sendiri untuk mengajar algoritma Kadane. Salah satu daripada vektor di atas, dengan jumlah keseluruhannya, terdapat dalam jadual ini:
| Data | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | lima belas | 4 | -8 | -lima belas | -22 |
| Jumlah 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 |
Menjalankan Jumlah untuk indeks ialah jumlah semua nilai sebelumnya termasuk nilai untuk indeks. Terdapat dua jujukan dengan jumlah maksimum di sini. Mereka ialah {5, 7}, yang memberikan jumlah 12, dan {6, 5, 10, -5, 15, 4}, yang memberikan jumlah 35. Urutan yang memberikan jumlah 35 ialah apa yang dikehendaki .
Perhatikan bahawa untuk jumlah berjalan, terdapat dua puncak iaitu nilai, 12 dan 27. Puncak ini sepadan dengan indeks terakhir kedua-dua jujukan.
Jadi, idea algoritma Kadane ialah melakukan jumlah larian sambil membandingkan jumlah maksimum yang ditemui, bergerak dari kiri ke kanan dalam tatasusunan yang diberikan.
Satu lagi vektor dari atas, dengan jumlah berjalannya, terdapat dalam jadual ini:
Terdapat dua jujukan dengan jumlah maksimum. Ia adalah {10, 15, 9}, yang memberikan jumlah 34; dan {4, 6, 3, 2, 8, 3} yang memberikan jumlah 26. Urutan yang memberikan hasil tambah 34, ialah apa yang dikehendaki.
Perhatikan bahawa untuk jumlah larian, terdapat dua puncak iaitu nilai, 30 dan 13. Puncak ini sepadan dengan indeks terakhir kedua-dua jujukan.
Sekali lagi, idea algoritma Kadane adalah untuk melakukan jumlah larian sambil membandingkan jumlah maksimum yang ditemui, bergerak dari kiri ke kanan dalam tatasusunan yang diberikan.
Kod oleh Algoritma Kadane dalam C++
Kod yang diberikan dalam bahagian artikel ini tidak semestinya yang digunakan oleh Kadane. Walau bagaimanapun, ia adalah dengan algoritmanya. Program seperti banyak program C++ lain, akan bermula dengan:
#include#include
menggunakan ruang nama std;
Terdapat kemasukan perpustakaan iostream, yang bertanggungjawab untuk input dan output. Ruang nama standard digunakan.
Idea algoritma Kadane adalah untuk mempunyai jumlah berjalan sambil membandingkan jumlah maksimum seperti yang ditemui, bergerak dari kiri ke kanan dalam tatasusunan yang diberikan. Fungsi untuk algoritma ialah:
int maxSunArray ( vektor < int > & A ) {int N = A.saiz ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
untuk ( int i = 1 ; i < N; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // boleh lebih kecil daripada A [ i ]
jika ( A [ i ] > tempRunTotal )
runTotal = A [ i ] ; // dalam kes A [ i ] adalah lebih besar daripada jumlah berjalan
lain
runTotal = tempRunTotal;
jika ( runTotal > maxAmount ) // membandingkan semua jumlah maksimum
maxSum = runTotal;
}
kembali maxAmount;
}
Saiz, N tatasusunan (vektor) yang diberikan ditentukan. Pembolehubah, maxSum ialah salah satu jumlah maksimum yang mungkin. Suatu tatasusunan mempunyai sekurang-kurangnya satu jumlah maksimum. Pembolehubah, runTotal mewakili jumlah berjalan pada setiap indeks. Kedua-duanya dimulakan dengan nilai pertama tatasusunan. Dalam algoritma ini, jika nilai seterusnya dalam tatasusunan adalah lebih besar daripada jumlah larian maka nilai seterusnya itu akan menjadi jumlah larian baharu.
Terdapat satu gelung untuk utama. Pengimbasan bermula dari 1 dan bukan sifar kerana permulaan pembolehubah, maxSum dan runTotal kepada A[0] yang merupakan elemen pertama tatasusunan yang diberikan.
Dalam gelung untuk, pernyataan pertama menentukan jumlah larian sementara dengan menambahkan nilai semasa kepada jumlah terkumpul semua nilai sebelumnya.
Seterusnya, terdapat binaan if/else. Jika nilai semasa sahaja lebih besar daripada jumlah berjalan setakat ini, maka nilai tunggal itu menjadi jumlah berjalan. Ini berguna terutamanya jika semua nilai dalam tatasusunan yang diberikan adalah negatif. Dalam kes ini, nilai negatif tertinggi sahaja akan menjadi nilai maksimum (jawapan). Jika nilai semasa sahaja tidak lebih besar daripada jumlah larian sementara setakat ini, maka jumlah larian menjadi jumlah larian sebelumnya ditambah nilai semasa, – ini bahagian lain daripada konstruk if/else.
Segmen kod terakhir dalam gelung untuk memilih antara mana-mana jumlah maksimum sebelumnya untuk jujukan sebelumnya (sub-tatasusunan) dan mana-mana jumlah maksimum semasa untuk jujukan semasa. Oleh itu, nilai yang lebih tinggi dipilih. Boleh terdapat lebih daripada satu jumlah sub-array maksimum. Ambil perhatian bahawa jumlah berjalan akan naik dan turun, kerana tatasusunan diimbas dari kiri ke kanan. Ia jatuh apabila ia memenuhi nilai negatif.
Jumlah sub-array maksimum terakhir yang dipilih dikembalikan selepas gelung untuk.
Kandungan untuk fungsi utama C++ yang sesuai, untuk fungsi algoritma Kadane ialah:
vektor < int > A = { 5 , - 7 , 3 , 5 , - dua , 4 , - 1 } ; // { 3 , 5 , - dua , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << endl;
vektor < int > B = { - dua , 1 , - 3 , 4 , - 1 , dua , 1 , - 5 , 4 } ; // { 4 , − 1 , dua , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vektor < int > C = { 3 , dua , - 6 , 4 , 0 } ; // { 3 , dua } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vektor < int > D = { 3 , dua , 6 , - 1 , 4 , 5 , - 1 , dua } ; // { 3 , dua , 6 , - 1 , 4 , 5 , - 1 , dua } - > 5
int ret4 = maxSunArray ( D ) ;
cout << jaring4 << endl;
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , lima belas , 4 , - 8 , - lima belas , - 22 } ; // { 6 , 5 , 10 , - 5 , lima belas , 4 } - > 35
int ret5 = maxSunArray ( DAN ) ;
cout << ret5 << endl;
vektor < int > F = { - 4 , 10 , lima belas , 9 , - 5 , - dua puluh , - 3 , - 12 , - 3 , 4 , 6 , 3 , dua , 8 , 3 , - 5 , - dua } ; // { 10 , lima belas , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << betul 6 << endl;
Dengan itu, output akan menjadi:
10
6
5
dua puluh
35
3. 4
Setiap baris jawapan di sini, sepadan dengan tatasusunan yang diberikan, mengikut urutan.
Kesimpulan
Kerumitan masa untuk algoritma Kadane ialah O(n), dengan n ialah bilangan elemen dalam tatasusunan yang diberikan. Kerumitan masa ini adalah yang terpantas untuk masalah sub-array maksimum. Terdapat algoritma lain yang lebih perlahan. Idea algoritma Kadane adalah untuk melakukan jumlah larian, sambil membandingkan jumlah maksimum yang ditemui, bergerak dari kiri ke kanan dalam tatasusunan yang diberikan. Jika nilai semasa sahaja lebih besar daripada jumlah berjalan setakat ini, maka nilai tunggal itu menjadi jumlah berjalan baharu. Jika tidak, jumlah larian baharu ialah jumlah larian sebelumnya ditambah elemen semasa, seperti yang dijangkakan, kerana tatasusunan yang diberikan diimbas.
Boleh terdapat lebih daripada satu jumlah maksimum, untuk sub-tatasusunan yang berbeza. Jumlah maksimum tertinggi, untuk semua sub-tatasusunan yang mungkin, dipilih.
Apakah indeks pengehadan untuk julat jumlah maksimum yang dipilih? - Itu adalah perbincangan untuk masa yang lain!
Chrys