Tantangan ini adalah dari tes masuk ke kursus keamanan cyber nomor tertutup. Lagi pula itu tidak ada hubungannya dengan keamanan cyber, itu hanya untuk menguji para siswa logika dan keterampilan pengkodean.
Tugas
Tulis sebuah program yang menghapus entri dari array sehingga nilai-nilai yang tersisa diurutkan dalam urutan menurun ketat dan jumlah mereka adalah dimaksimalkan di antara semua kemungkinan urutan penurunan lainnya.
Masukan dan keluaran
Masukan akan menjadi sebuah array nilai integer ketat lebih besar dari 0
dan semua berbeda satu sama lain . Anda bebas memilih apakah akan membaca input dari file, baris perintah atau stdin.
Output akan menjadi subarray descending- sort dari input yang jumlahnya lebih besar dari subarray descending-sort yang mungkin lainnya.
Catatan: [5, 4, 3, 2]
adalah subarray [5, 4, 1, 3, 2]
, bahkan jika 4
dan 3
tidak berdekatan. Hanya karena 1
sudah muncul.
Solusi bruteforce
Solusi paling sederhana tentu saja akan beralih di antara semua kombinasi yang mungkin dari array yang diberikan dan mencari yang diurutkan dengan jumlah terbesar, yaitu, dengan Python :
import itertools
def best_sum_desc_subarray(ary):
best_sum_so_far = 0
best_subarray_so_far = []
for k in range(1, len(ary)):
for comb in itertools.combinations(ary, k):
if sum(comb) > best_sum_so_far and all(comb[j] > comb[j+1] for j in range(len(comb)-1)):
best_subarray_so_far = list(comb)
best_sum_so_far = sum(comb)
return best_subarray_so_far
Sayangnya, sejak memeriksa apakah array diurutkan, dan menghitung jumlah unsur itu adalah dan karena operasi ini akan dilakukan kali untuk dari ke , kompleksitas waktu asimtotik akan
Tantangan
Tujuan Anda adalah untuk mencapai kompleksitas waktu yang lebih baik daripada bruteforce di atas. Solusi dengan kompleksitas waktu asimptotik terkecil adalah pemenang tantangan. Jika dua solusi memiliki kompleksitas waktu asimptotik yang sama, pemenang akan menjadi satu dengan kompleksitas spasial asimptotik terkecil.
Catatan: Anda dapat mempertimbangkan membaca, menulis, dan membandingkan atom bahkan dalam jumlah besar.
Catatan: Jika ada dua atau lebih solusi mengembalikan salah satu dari mereka.
Uji kasus
Input: [200, 100, 400]
Output: [400]
Input: [4, 3, 2, 1, 5]
Output: [4, 3, 2, 1]
Input: [50, 40, 30, 20, 10]
Output: [50, 40, 30, 20, 10]
Input: [389, 207, 155, 300, 299, 170, 158, 65]
Output: [389, 300, 299, 170, 158, 65]
Input: [19, 20, 2, 18, 13, 14, 8, 9, 4, 6, 16, 1, 15, 12, 3, 7, 17, 5, 10, 11]
Output: [20, 18, 16, 15, 12, 7, 5]
Input: [14, 12, 24, 21, 6, 10, 19, 1, 5, 8, 17, 7, 9, 15, 23, 20, 25, 11, 13, 4, 3, 22, 18, 2, 16]
Output: [24, 21, 19, 17, 15, 13, 4, 3, 2]
Input: [25, 15, 3, 6, 24, 30, 23, 7, 1, 10, 16, 29, 12, 13, 22, 8, 17, 14, 20, 11, 9, 18, 28, 21, 26, 27, 4, 2, 19, 5]
Output: [25, 24, 23, 22, 17, 14, 11, 9, 4, 2]
Jawaban:
Perl
Ini harus O (n ^ 2) dalam waktu dan O (n) dalam ruang
Berikan angka yang dipisahkan oleh spasi pada satu baris ke STDIN
sumber
Bagaimana itu bekerja
bestSubarrays xs
adalah urutan subarraysxs
yang berada di perbatasan efisien {jumlah terbesar, elemen pertama terkecil}, dipesan dari kiri ke kanan dengan meningkatkan jumlah dan meningkatkan elemen pertama.Untuk pergi dari
bestSubarrays xs
kebestSubarrays (x:xs)
, kitax
, dan sisi kanan dengan elemen pertama lebih besar darix
,x
ke subarray paling kanan di sisi kiri,sumber
Jawaban ini berkembang pada jawaban Ton Hospel.
Masalahnya dapat diselesaikan dengan pemrograman dinamis menggunakan perulangan
dimana( asaya) adalah urutan input dan T( i ) jumlah yang dapat dicapai secara maksimal dari setiap sub-urutan menurun yang diakhiri dengan indeks saya . Solusi aktual kemudian dapat ditelusuri menggunakanT , seperti pada kode karat berikut.
Cobalah online!
sumber