Kadane Algorithim

Kadane-Algorithim

Ini adalah solusi JavaScript untuk salah satu algoritim pemrograman dinamis yang terkenal.

Pernyataan masalah

Diberikan array a = {a1, a2,…, an} dari elemen n, temukan jumlah maksimum yang mungkin dari a

Subarray subarray yang berdekatan (tidak harus berdekatan) subarray.
Subarrays/selanjutnya kosong tidak boleh dipertimbangkan.

Video YouTube ini oleh Ben Wright mungkin berguna untuk memahami algoritma Kadane untuk subarray maksimum dalam urutan 1-D.

Format input

Baris pertama dari input memiliki kasus integer T. T mengikuti. Setiap kasus uji dimulai dengan integer N. di baris berikutnya, n bilangan bulat mengikuti mewakili elemen array A.

Kendala:

1≤T≤10
1≤n≤105
−104≤ai≤104

Subarray dan selanjutnya yang Anda pertimbangkan harus memiliki setidaknya satu elemen.

Format output

Dua, ruang terpisah, bilangan bulat yang menunjukkan subarray maksimum yang berdekatan dan tidak bersebelahan. Setidaknya satu bilangan bulat harus dipilih dan dimasukkan ke dalam subarray (ini mungkin diperlukan dalam kasus di mana semua elemen negatif).

Input sampel

2
4
1 2 3 4
6
2 -1 2 3 4 -5

Output sampel

10 10
10 11

Penjelasan

Dalam kasus pertama: jumlah maksimal untuk elemen yang berdekatan dan tidak kontigu adalah jumlah dari semua elemen (karena semuanya positif).

Dalam kasus kedua: [2 -1 2 3 4] -> Ini membentuk sub -array yang berdekatan dengan jumlah maksimum. Untuk jumlah maksimal dari kelompok elemen yang tidak perlu yang tidak perlu, cukup tambahkan semua elemen positif.