b belajar.myudak
☰ Daftar soalRoadmap‹›

Subarray Jumlah Maksimum

sedangDP 1 DimensiAnalisis dan Strategi Algoritma

Cari subarray kontigu (minimal satu elemen) yang jumlahnya paling besar, lalu kembalikan jumlah itu.

[-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6   // [4, -1, 2, 1]

Brute force O(n2)O(n^2) atau O(n3)O(n^3) mudah. Bisakah O(n)O(n)?

Topik
dynamic programmingarray
Petunjuk 1

Untuk setiap posisi i, berapa jumlah terbesar subarray yang BERAKHIR di i?

Petunjuk 2

best(i) = max(nums[i], best(i−1) + nums[i]). Ini algoritma Kadane, O(n).

Pengaturan editor

Ukuran font
Ukuran huruf di editor.
Ukuran tab
Lebar indentasi. Otomatis: 2 spasi untuk TypeScript, 4 untuk Python.
Key bindings
Ganti ke mode Vim.
Nomor baris relatif
Nomor baris dihitung dari posisi kursor (berguna untuk gerakan Vim).
Word wrap
Baris panjang dilipat agar muat di lebar editor.
IntelliSense
Saran kode otomatis saat mengetik (Ctrl+Spasi tetap bisa dipakai saat mati).

Nilai ditulis sebagai JSON. Output yang diharapkan dihitung dari solusi referensi.