Objek memungkinkan Anda menyimpan kumpulan nilai yang dikunci. Tidak apa-apa.
Namun seringkali kita menemukan bahwa kita memerlukan koleksi yang terurut , di mana kita memiliki elemen ke-1, ke-2, ke-3, dan seterusnya. Misalnya, kita memerlukannya untuk menyimpan daftar sesuatu: pengguna, barang, elemen HTML, dll.
Tidak nyaman menggunakan objek di sini, karena tidak menyediakan metode untuk mengatur urutan elemen. Kita tidak dapat menyisipkan properti baru “di antara” properti yang sudah ada. Objek tidak dimaksudkan untuk penggunaan seperti itu.
Terdapat struktur data khusus bernama Array , untuk menyimpan koleksi yang dipesan.
Ada dua sintaks untuk membuat array kosong:
biarkan arr = Array baru(); biarkan arr = [];
Hampir sepanjang waktu, sintaks kedua digunakan. Kami dapat menyediakan elemen awal dalam tanda kurung:
biarkan buah-buahan = ["Apel", "Jeruk", "Plum"];
Elemen array diberi nomor, dimulai dari nol.
Kita bisa mendapatkan suatu elemen berdasarkan nomornya dalam tanda kurung siku:
biarkan buah-buahan = ["Apel", "Jeruk", "Plum"]; peringatan( buah-buahan[0] ); // apel peringatan( buah-buahan[1] ); // Oranye waspada( buah-buahan[2] ); // Prem
Kita dapat mengganti elemen:
buah-buahan[2] = 'Pir'; // sekarang ["Apel", "Oranye", "Pir"]
…Atau tambahkan yang baru ke array:
buah-buahan[3] = 'Lemon'; // sekarang ["Apel", "Jeruk", "Pir", "Lemon"]
Jumlah total elemen dalam array adalah length :
biarkan buah-buahan = ["Apel", "Jeruk", "Plum"]; alert( buah-buahan.panjang ); // 3
Kita juga bisa menggunakan alert untuk menampilkan keseluruhan array.
biarkan buah-buahan = ["Apel", "Jeruk", "Plum"]; waspada( buah-buahan); // Apel,Jeruk,Plum
Array dapat menyimpan elemen jenis apa pun.
Misalnya:
// campuran nilai
let arr = [ 'Apple', { nama: 'John' }, true, function() { alert('halo'); } ];
// ambil objek di indeks 1 lalu tampilkan namanya
peringatan( arr[1].nama ); // Yohanes
// ambil fungsi di indeks 3 dan jalankan
arr[3](); // HaloDi belakang koma
Array, seperti halnya objek, dapat diakhiri dengan koma:
biarkan buah = [ "Apel", "Oranye", "Prem", ];
Gaya “trailing comma” memudahkan penyisipan/penghapusan item, karena semua baris menjadi sama.
Tambahan baru-baru ini
Ini adalah tambahan terbaru pada bahasa ini. Browser lama mungkin memerlukan polyfill.
Katakanlah kita menginginkan elemen terakhir dari array.
Beberapa bahasa pemrograman mengizinkan penggunaan indeks negatif untuk tujuan yang sama, seperti fruits[-1] .
Meskipun dalam JavaScript itu tidak akan berfungsi. Hasilnya undefined , karena indeks dalam tanda kurung siku diperlakukan secara harfiah.
Kita dapat secara eksplisit menghitung indeks elemen terakhir dan kemudian mengaksesnya: fruits[fruits.length - 1] .
biarkan buah-buahan = ["Apel", "Jeruk", "Plum"]; alert( buah-buahan[buah-buahan.panjang-1] ); // Prem
Agak rumit, bukan? Kita perlu menulis nama variabel dua kali.
Untungnya, ada sintaks yang lebih pendek: fruits.at(-1) :
biarkan buah-buahan = ["Apel", "Jeruk", "Plum"]; // sama seperti buah-buahan[buah-buahan.panjang-1] waspada( buah-buahan.at(-1) ); // Prem
Dengan kata lain, arr.at(i) :
persis sama dengan arr[i] , jika i >= 0 .
untuk nilai negatif i , ia mundur dari akhir larik.
Antrian adalah salah satu penggunaan array yang paling umum. Dalam ilmu komputer, ini berarti kumpulan elemen terurut yang mendukung dua operasi:
push menambahkan elemen ke akhir.
shift dapatkan elemen dari awal, majukan antrian, sehingga elemen ke-2 menjadi elemen ke-1.
Array mendukung kedua operasi tersebut.
Dalam praktiknya kita sangat sering membutuhkannya. Misalnya, antrian pesan yang perlu ditampilkan di layar.
Ada kasus penggunaan lain untuk array – struktur data bernama tumpukan.
Ini mendukung dua operasi:
push menambahkan elemen di akhir.
pop mengambil elemen dari akhir.
Jadi elemen baru selalu ditambahkan atau diambil dari “akhir”.
Tumpukan biasanya diilustrasikan sebagai sekumpulan kartu: kartu baru ditambahkan ke atas atau diambil dari atas:
Untuk tumpukan, item yang terakhir didorong diterima terlebih dahulu, itu juga disebut prinsip LIFO (Last-In-First-Out). Untuk antrian, kami memiliki FIFO (First-In-First-Out).
Array dalam JavaScript dapat berfungsi baik sebagai antrian maupun sebagai tumpukan. Mereka memungkinkan Anda untuk menambah/menghapus elemen, baik ke/dari awal atau akhir.
Dalam ilmu komputer, struktur data yang memungkinkan hal ini disebut deque.
Metode yang bekerja dengan akhir array:
pop
Ekstrak elemen terakhir array dan kembalikan:
biarkan buah = ["Apel", "Jeruk", "Pir"]; waspada( buah-buahan.pop() ); // hapus "Pear" dan beri peringatan waspada( buah-buahan); // Apel, Jeruk
fruits.pop() dan fruits.at(-1) mengembalikan elemen terakhir array, namun fruits.pop() juga memodifikasi array dengan menghapusnya.
push
Tambahkan elemen ke akhir array:
biarkan buah = ["Apel", "Jeruk"];
buah-buahan.push("Pir");
waspada( buah-buahan); // Apel, Jeruk, Pir Panggilan fruits.push(...) sama dengan fruits[fruits.length] = ... .
Metode yang bekerja dengan awal array:
shift
Ekstrak elemen pertama array dan kembalikan:
biarkan buah = ["Apel", "Jeruk", "Pir"]; waspada( buah-buahan.shift() ); // hapus Apple dan beri peringatan waspada( buah-buahan); // Jeruk, Pir
unshift
Tambahkan elemen ke awal array:
biarkan buah = ["Jeruk", "Pir"];
buah-buahan.unshift('Apel');
waspada( buah-buahan); // Apel, Jeruk, Pir Metode push dan unshift dapat menambahkan beberapa elemen sekaligus:
biarkan buah = ["Apel"];
buah-buahan.push("Jeruk", "Persik");
buah-buahan.unshift("Nanas", "Lemon");
// ["Nanas", "Lemon", "Apel", "Jeruk", "Persik"]
waspada( buah-buahan); Array adalah jenis objek khusus. Tanda kurung siku yang digunakan untuk mengakses properti arr[0] sebenarnya berasal dari sintaksis objek. Itu pada dasarnya sama dengan obj[key] , di mana arr adalah objeknya, sedangkan angka digunakan sebagai kunci.
Mereka memperluas objek yang menyediakan metode khusus untuk bekerja dengan kumpulan data yang dipesan dan juga properti length . Namun pada intinya ia tetaplah sebuah objek.
Ingat, hanya ada delapan tipe data dasar dalam JavaScript (lihat bab Tipe data untuk info lebih lanjut). Array adalah sebuah objek dan dengan demikian berperilaku seperti sebuah objek.
Misalnya, ini disalin dengan referensi:
biarkan buah = ["Pisang"]
misalkan arr = buah-buahan; // salin dengan referensi (dua variabel mereferensikan array yang sama)
waspada( arr === buah-buahan ); // BENAR
arr.push("Pir"); // memodifikasi array dengan referensi
waspada( buah-buahan); // Pisang, Pir - 2 item sekarang…Tetapi apa yang membuat array benar-benar istimewa adalah representasi internalnya. Mesin mencoba untuk menyimpan elemen-elemennya di area memori yang berdekatan, satu demi satu, seperti yang digambarkan pada ilustrasi di bab ini, dan ada optimasi lain juga, untuk membuat array bekerja sangat cepat.
Namun semuanya akan rusak jika kita berhenti bekerja dengan array sebagai “koleksi terurut” dan mulai mengerjakannya seolah-olah itu adalah objek biasa.
Misalnya, secara teknis kita bisa melakukan ini:
biarkan buah = []; // membuat sebuah array buah-buahan[99999] = 5; // menetapkan properti dengan indeks yang jauh lebih besar daripada panjangnya buah.umur = 25; // membuat properti dengan nama arbitrer
Itu mungkin saja, karena array adalah objek pada dasarnya. Kita dapat menambahkan properti apa pun ke dalamnya.
Namun mesin akan melihat bahwa kita bekerja dengan array seperti halnya objek biasa. Pengoptimalan khusus array tidak cocok untuk kasus seperti itu dan akan dinonaktifkan, sehingga manfaatnya akan hilang.
Cara menyalahgunakan array:
Tambahkan properti non-numerik seperti arr.test = 5 .
Buat lubang, seperti: tambahkan arr[0] lalu arr[1000] (dan tidak ada apa pun di antaranya).
Isi array dalam urutan terbalik, seperti arr[1000] , arr[999] dan seterusnya.
Harap anggap array sebagai struktur khusus untuk bekerja dengan data yang dipesan . Mereka menyediakan metode khusus untuk itu. Array disetel dengan cermat di dalam mesin JavaScript agar berfungsi dengan data terurut yang berdekatan, silakan gunakan dengan cara ini. Dan jika Anda memerlukan kunci arbitrer, kemungkinan besar Anda benar-benar memerlukan objek biasa {} .
Metode push/pop berjalan cepat, sedangkan shift/unshift berjalan lambat.
Mengapa bekerja dengan akhir array lebih cepat dibandingkan dengan permulaannya? Mari kita lihat apa yang terjadi selama eksekusi:
buah-buahan.shift(); // ambil 1 elemen dari awal
Mengambil dan menghapus elemen dengan indeks 0 saja tidak cukup. Elemen lain juga perlu diberi nomor ulang.
Operasi shift harus melakukan 3 hal:
Hapus elemen dengan indeks 0 .
Pindahkan semua elemen ke kiri, beri nomor ulang dari indeks 1 menjadi 0 , dari 2 menjadi 1 dan seterusnya.
Perbarui properti length .
Semakin banyak elemen dalam array, semakin banyak waktu untuk memindahkannya, semakin banyak operasi dalam memori.
Hal serupa terjadi dengan unshift : untuk menambahkan elemen ke awal array, pertama-tama kita perlu memindahkan elemen yang ada ke kanan, sehingga meningkatkan indeksnya.
Dan ada apa dengan push/pop ? Mereka tidak perlu memindahkan apa pun. Untuk mengekstrak elemen dari akhir, metode pop membersihkan indeks dan memperpendek length .
Tindakan untuk operasi pop :
buah-buahan.pop(); // ambil 1 elemen dari akhir
Metode pop tidak perlu memindahkan apa pun, karena elemen lain tetap menjaga indeksnya. Itu sebabnya ini sangat cepat.
Hal serupa dengan metode push .
Salah satu cara tertua untuk menggilir item array adalah perulangan for pada indeks:
let arr = ["Apel", "Jeruk", "Pir"];
for (misalkan i = 0; i < arr.length; i++) {
waspada( arr[i] );
} Tapi untuk array ada bentuk loop lain, for..of :
biarkan buah-buahan = ["Apel", "Jeruk", "Plum"];
// mengulangi elemen array
untuk (biarkan buah dari buah) {
waspada( buah );
} for..of tidak memberikan akses ke nomor elemen saat ini, hanya nilainya, tetapi dalam banyak kasus itu sudah cukup. Dan itu lebih pendek.
Secara teknis, karena array adalah objek, maka dimungkinkan juga untuk menggunakan for..in :
let arr = ["Apel", "Jeruk", "Pir"];
untuk (biarkan memasukkan arr) {
waspada( arr[kunci] ); // Apel, Jeruk, Pir
}Tapi itu sebenarnya ide yang buruk. Ada potensi masalah dengannya:
Perulangan for..in mengulangi semua properti , tidak hanya properti numerik.
Ada yang disebut objek “seperti array” di browser dan di lingkungan lain, yang terlihat seperti array . Artinya, mereka memiliki properti length dan indeks, tetapi mereka mungkin juga memiliki properti dan metode non-numerik lainnya, yang biasanya tidak kita perlukan. Loop for..in akan mencantumkannya. Jadi jika kita perlu bekerja dengan objek seperti array, maka properti “ekstra” ini bisa menjadi masalah.
Perulangan for..in dioptimalkan untuk objek umum, bukan array, sehingga 10-100 kali lebih lambat. Tentu saja masih sangat cepat. Percepatan mungkin hanya penting dalam kemacetan. Tapi tetap saja kita harus mewaspadai perbedaannya.
Secara umum, kita tidak boleh menggunakan for..in untuk array.
Properti length secara otomatis diperbarui ketika kita mengubah array. Tepatnya, ini sebenarnya bukan penghitungan nilai dalam array, melainkan indeks numerik terbesar ditambah satu.
Misalnya, satu elemen dengan indeks besar memberikan panjang yang besar:
biarkan buah = []; buah-buahan[123] = "Apel"; alert( buah-buahan.panjang ); // 124
Perhatikan bahwa kami biasanya tidak menggunakan array seperti itu.
Hal menarik lainnya tentang properti length adalah dapat ditulisi.
Jika kita meningkatkannya secara manual, tidak ada hal menarik yang terjadi. Tetapi jika kita menguranginya, arraynya terpotong. Prosesnya tidak dapat diubah, berikut contohnya:
misalkan arr = [1, 2, 3, 4, 5]; arr.panjang = 2; // potong menjadi 2 elemen waspada( arr ); // [1, 2] arr.panjang = 5; // mengembalikan panjang kembali waspada( arr[3] ); // tidak terdefinisi: nilai tidak kembali
Jadi, cara paling sederhana untuk menghapus array adalah: arr.length = 0; .
Ada satu sintaks lagi untuk membuat array:
let arr = new Array("Apple", "Pear", "etc"); Ini jarang digunakan, karena tanda kurung siku [] lebih pendek. Juga, ada fitur rumit di dalamnya.
Jika new Array dipanggil dengan argumen tunggal berupa angka, maka Array baru akan dibuat tanpa item, tetapi dengan panjang tertentu .
Mari kita lihat bagaimana seseorang dapat menembak kakinya sendiri:
biarkan arr = Array baru(2); // apakah ini akan membuat array [2] ? waspada( arr[0] ); // belum diartikan! tidak ada elemen. waspada( arr.panjang ); // panjang 2
Untuk menghindari kejutan seperti itu, kita biasanya menggunakan tanda kurung siku, kecuali kita benar-benar tahu apa yang kita lakukan.
Array dapat memiliki item yang juga merupakan array. Kita dapat menggunakannya untuk array multidimensi, misalnya untuk menyimpan matriks:
misalkan matriks = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]; peringatan( matriks[0][1] ); // 2, nilai kedua dari array dalam pertama
Array memiliki implementasi metode toString sendiri yang mengembalikan daftar elemen yang dipisahkan koma.
Misalnya:
misalkan arr = [1, 2, 3]; waspada( arr ); // 1,2,3 peringatan( String(arr) === '1,2,3' ); // BENAR
Juga, mari kita coba ini:
peringatan( [] + 1 ); // "1" peringatan( [1] + 1 ); // "11" peringatan( [1,2] + 1 ); // "1,21"
Array tidak memiliki Symbol.toPrimitive , tidak juga valueOf yang layak, array hanya mengimplementasikan konversi toString , jadi di sini [] menjadi string kosong, [1] menjadi "1" dan [1,2] menjadi "1,2" .
Ketika operator biner plus "+" menambahkan sesuatu ke sebuah string, ia juga mengubahnya menjadi string, sehingga langkah selanjutnya terlihat seperti ini:
peringatan(""+1); // "1"
peringatan("1"+1); // "11"
peringatan("1,2"+1); // "1,21" Array dalam JavaScript, tidak seperti beberapa bahasa pemrograman lainnya, tidak boleh dibandingkan dengan operator == .
Operator ini tidak memiliki perlakuan khusus untuk array, ia bekerja dengannya seperti halnya objek apa pun.
Mari kita ingat aturannya:
Dua objek sama == hanya jika keduanya merujuk ke objek yang sama.
Jika salah satu argumen == adalah objek, dan argumen lainnya adalah primitif, maka objek tersebut akan dikonversi menjadi primitif, seperti yang dijelaskan dalam bab Konversi objek ke primitif.
…Dengan pengecualian null dan undefined yang sama dengan == satu sama lain dan tidak ada yang lain.
Perbandingan ketat === bahkan lebih sederhana, karena tidak mengubah tipe.
Jadi, jika kita membandingkan array dengan == , array tersebut tidak akan pernah sama, kecuali kita membandingkan dua variabel yang mereferensikan array yang sama persis.
Misalnya:
peringatan( [] == [] ); // PALSU peringatan( [0] == [0] ); // PALSU
Array ini secara teknis merupakan objek yang berbeda. Jadi mereka tidak setara. Operator == tidak melakukan perbandingan item demi item.
Perbandingan dengan primitif mungkin juga memberikan hasil yang aneh:
peringatan( 0 == [] ); // BENAR
peringatan('0' == [] ); // PALSU Di sini, dalam kedua kasus, kita membandingkan primitif dengan objek array. Jadi array [] diubah menjadi primitif untuk tujuan perbandingan dan menjadi string kosong '' .
Kemudian proses perbandingan dilanjutkan dengan primitif, seperti yang dijelaskan pada bab Konversi Jenis:
// setelah [] diubah menjadi ''
peringatan( 0 == '' ); // benar, karena '' dikonversi ke angka 0
peringatan('0' == '' ); // salah, tidak ada konversi tipe, string berbedaJadi, bagaimana cara membandingkan array?
Sederhana saja: jangan gunakan operator == . Sebaliknya, bandingkan item demi item dalam satu putaran atau gunakan metode iterasi yang dijelaskan di bab berikutnya.
Array adalah jenis objek khusus, yang cocok untuk menyimpan dan mengelola item data yang diurutkan.
Deklarasi:
// tanda kurung siku (biasa) biarkan arr = [item1, item2...]; // Array baru (sangat jarang) biarkan arr = Array baru(item1, item2...);
Panggilan ke new Array(number) membuat array dengan panjang tertentu, tetapi tanpa elemen.
Properti length adalah panjang array atau, tepatnya, indeks numerik terakhirnya ditambah satu. Ini disesuaikan secara otomatis dengan metode array.
Jika kita memperpendek length secara manual, array akan terpotong.
Mendapatkan elemen:
kita bisa mendapatkan elemen berdasarkan indeksnya, seperti arr[0]
kita juga dapat menggunakan metode at(i) yang memungkinkan indeks negatif. Untuk nilai i yang negatif, ia mundur dari akhir larik. Jika i >= 0 , cara kerjanya sama seperti arr[i] .
Kita dapat menggunakan array sebagai deque dengan operasi berikut:
push(...items) menambahkan items ke akhir.
pop() menghapus elemen dari akhir dan mengembalikannya.
shift() menghapus elemen dari awal dan mengembalikannya.
unshift(...items) menambahkan items ke awal.
Untuk mengulang elemen array:
for (let i=0; i<arr.length; i++) – bekerja paling cepat, kompatibel dengan browser lama.
for (let item of arr) – sintaks modern untuk item saja,
for (let i in arr) – jangan pernah gunakan.
Untuk membandingkan array, jangan gunakan operator == (serta > , < dan lainnya), karena operator tersebut tidak memiliki perlakuan khusus untuk array. Mereka memperlakukannya seperti benda apa pun, dan itu bukan yang biasanya kita inginkan.
Sebagai gantinya, Anda dapat menggunakan for..of loop untuk membandingkan array item demi item.
Kita akan melanjutkan dengan array dan mempelajari lebih banyak metode untuk menambah, menghapus, mengekstrak elemen dan mengurutkan array di bab berikutnya Metode array.
pentingnya: 3
Apa yang akan ditampilkan kode ini?
biarkan buah-buahan = ["Apel", "Pir", "Jeruk"];
// memasukkan nilai baru ke dalam "salinan"
biarkan keranjang belanja = buah-buahan;
shoppingCart.push("Pisang");
// apa isi buah-buahan?
alert( buah-buahan.panjang ); // ?
Hasilnya adalah 4 :
biarkan buah-buahan = ["Apel", "Pir", "Jeruk"];
biarkan keranjang belanja = buah-buahan;
shoppingCart.push("Pisang");
alert( buah-buahan.panjang ); // 4 Itu karena array adalah objek. Jadi shoppingCart dan fruits adalah referensi ke array yang sama.
pentingnya: 5
Mari kita coba 5 operasi array.
Buat styles array dengan item "Jazz" dan "Blues".
Tambahkan “Rock-n-Roll” di akhir.
Ganti nilai di tengah dengan “Klasik”. Kode Anda untuk menemukan nilai tengah harus berfungsi untuk array apa pun dengan panjang ganjil.
Hapus nilai pertama dari array dan tunjukkan.
Tambahkan Rap dan Reggae ke array.
Array dalam proses:
Jazz, Blues Jazz, Blues, Rock n Roll Jazz, Klasik, Rock-n-Roll Klasik, Rock-n-Roll Rap, Reggae, Klasik, Rock-n-Roll
biarkan gaya = ["Jazz", "Blues"];
gaya.push("Rock-n-Roll");
gaya[Matematika.lantai((gaya.panjang - 1) / 2)] = "Klasik";
peringatan( gaya.shift() );
style.unshift("Rap", "Reggae");pentingnya: 5
Apa hasilnya? Mengapa?
misalkan arr = ["a", "b"];
arr.push(fungsi() {
waspada( ini );
});
arr[2](); // ?
Panggilan arr[2]() secara sintaksis adalah obj[method]() yang bagus, dalam peran obj kita memiliki arr , dan dalam peran method yang kita miliki 2 .
Jadi kita memanggil fungsi arr[2] sebagai metode objek. Secara alami, ia menerima this dengan merujuk pada objek arr dan mengeluarkan array:
misalkan arr = ["a", "b"];
arr.push(fungsi() {
waspada( ini );
})
arr[2](); // a,b,fungsi(){...}Array memiliki 3 nilai: awalnya memiliki dua, ditambah fungsinya.
pentingnya: 4
Tulis fungsi sumInput() yang:
Meminta nilai kepada pengguna menggunakan prompt dan menyimpan nilai dalam array.
Selesai menanyakan kapan pengguna memasukkan nilai non-numerik, string kosong, atau menekan “Batal”.
Menghitung dan mengembalikan jumlah item array.
PS A nol 0 adalah angka yang valid, mohon jangan hentikan input pada nol.
Jalankan demonya
Harap perhatikan detail solusi yang halus namun penting. Kami tidak langsung mengonversi value menjadi angka setelah prompt , karena setelah value = +value kami tidak akan dapat membedakan string kosong (tanda berhenti) dari nol (angka valid). Kami melakukannya nanti.
fungsi jumlahInput() {
misalkan angka = [];
sementara (benar) {
let value = prompt("Tolong nomornya?", 0);
// haruskah kita membatalkannya?
if (nilai === "" || nilai === null || !isFinite(nilai)) istirahat;
angka.push(+nilai);
}
misalkan jumlah = 0;
for (biarkan banyaknya angka) {
jumlah += angka;
}
jumlah pengembalian;
}
peringatan(jumlahInput() );pentingnya: 2
Inputnya berupa array angka, misal arr = [1, -2, 3, 4, -9, 6] .
Tugasnya adalah: temukan subarray arr yang berdekatan dengan jumlah item maksimal.
Tulis fungsi getMaxSubSum(arr) yang akan mengembalikan jumlah tersebut.
Misalnya:
getMaxSubSum([-1, 2, 3, -9]) == 5 (jumlah item yang disorot) getMaxSubSum([2, -1, 2, 3, -9]) == 6 getMaxSubSum([-1, 2, 3, -9, 11]) == 11 getMaxSubSum([-2, -1, 1, 2]) == 3 getMaxSubSum([100, -9, 2, -3, 5]) == 100 getMaxSubSum([1, 2, 3]) == 6 (ambil semua)
Jika semua item negatif, berarti kita tidak mengambil satu pun (subarraynya kosong), jadi jumlahnya nol:
getMaxSubSum([-1, -2, -3]) = 0
Silakan coba memikirkan solusi cepat: O(n 2 ) atau bahkan O(n) jika Anda bisa.
Buka kotak pasir dengan tes.
Kita dapat menghitung semua subsum yang mungkin.
Cara termudah adalah dengan mengambil setiap elemen dan menghitung jumlah semua subarray mulai dari elemen tersebut.
Misalnya, untuk [-1, 2, 3, -9, 11] :
// Mulai dari -1: -1 -1 + 2 -1 + 2 + 3 -1 + 2 + 3 + (-9) -1 + 2 + 3 + (-9) + 11 // Mulai dari 2: 2 2 + 3 2+3+(-9) 2 + 3 + (-9) + 11 // Mulai dari 3: 3 3+(-9) 3+(-9)+11 // Mulai dari -9 -9 -9+11 // Mulai dari 11 11
Kode ini sebenarnya adalah loop bersarang: loop eksternal di atas elemen array, dan subsum penghitungan internal dimulai dengan elemen saat ini.
fungsi getMaxSubSum(arr) {
misalkan jumlah maksimal = 0; // jika kita tidak mengambil elemen apa pun, nol akan dikembalikan
for (misalkan i = 0; i < arr.length; i++) {
biarkan sumFixedStart = 0;
for (misalkan j = i; j < arr.length; j++) {
sumFixedStart += arr[j];
maxSum = Matematika.max(maxSum, sumFixedStart);
}
}
kembalikan maxSum;
}
peringatan( getMaxSubSum([-1, 2, 3, -9]) ); // 5
peringatan( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
peringatan( getMaxSubSum([-2, -1, 1, 2]) ); // 3
peringatan( getMaxSubSum([1, 2, 3]) ); // 6
peringatan( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100Solusinya memiliki kompleksitas waktu O(n 2 ). Dengan kata lain, jika kita memperbesar ukuran array sebanyak 2 kali, algoritma akan bekerja 4 kali lebih lama.
Untuk array besar (1000, 10.000 item atau lebih), algoritme seperti itu dapat menyebabkan kelesuan yang serius.
Mari kita jalankan array dan pertahankan jumlah parsial elemen saat ini dalam variabel s . Jika s menjadi negatif pada suatu saat, maka tetapkan s=0 . Maksimal dari semua s tersebut akan menjadi jawabannya.
Jika uraiannya terlalu kabur, silakan lihat kodenya, cukup singkat:
fungsi getMaxSubSum(arr) {
misalkan jumlah maksimal = 0;
misalkan jumlah parsial = 0;
for (biarkan item dari arr) {// untuk setiap item dari arr
Jumlah parsial += item; // tambahkan ke parsialSum
maxSum = Matematika.max(maxSum, parsialSum); // ingat maksimal
jika (Jumlah parsial < 0) Jumlah parsial = 0; // nol jika negatif
}
kembalikan maxSum;
}
peringatan( getMaxSubSum([-1, 2, 3, -9]) ); // 5
peringatan( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
peringatan( getMaxSubSum([-2, -1, 1, 2]) ); // 3
peringatan( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
peringatan( getMaxSubSum([1, 2, 3]) ); // 6
peringatan( getMaxSubSum([-1, -2, -3]) ); // 0Algoritme ini memerlukan tepat 1 array pass, sehingga kompleksitas waktunya adalah O(n).
Anda dapat menemukan informasi lebih rinci tentang algoritma di sini: Masalah subarray maksimum. Jika masih belum jelas mengapa itu berhasil, silakan lacak algoritmanya pada contoh di atas, lihat cara kerjanya, itu lebih baik daripada kata-kata apa pun.
Buka solusi dengan pengujian di kotak pasir.