Lanjut55 XPUnit 13: Pemrograman Dinamis, soal 2 dari 10
Untung Beruntun Terbesar
Cari rangkaian hari berturut-turut dengan total untung terbesar.
Warung kopi Pak Hasan mencatat untung dan rugi harian. Ia ingin tahu periode hari berturut-turut yang paling menguntungkan, misalnya untuk menebak musim ramai.
Masukan
Baris pertama berisi N (1 sampai 30000). Baris kedua berisi N bilangan bulat, untung harian dalam ribuan rupiah. Bilangan negatif berarti rugi.
Keluaran
Total terbesar dari rangkaian hari berturut-turut yang tidak kosong.
Contoh masukan dan keluaran
Contoh 1
Masukan
9 -2 1 -3 4 -1 2 1 -5 4
Keluaran
6
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Untuk setiap hari, pikirkan total terbaik dari rangkaian yang berakhir tepat di hari itu: lanjutkan rangkaian kemarin, atau mulai baru dari hari ini.
Petunjuk 2
Rangkaian kemarin hanya layak dilanjutkan bila totalnya positif.