Diberikan urutan bilangan bulat tidak kosong yang kosong, kembalikan urutan aritmatika dengan panjang maksimal.
Jika ada beberapa dari panjang maksimal yang sama, salah satunya dapat dikembalikan.
Definisi:
Sebuah aritmatika urutan urutan a(1),a(2),a(3),a(4),...
seperti yang ada adalah konstan c
sehingga a(m+1)-a(m) = c
untuk semua m
. Dengan kata lain: Perbedaan antara dua istilah selanjutnya adalah konstan.
Mengingat urutan b(1),b(2),b(3),b(4),...
sebuah subsequence adalah urutan b(s(1)),b(s(2)),b(s(3)),b(s(4)),...
di mana 1 <= s(1)
dan s(m) < s(m+1)
untuk semua m
. Dengan kata lain: Ambil urutan asli dan hapus entri sebanyak yang Anda inginkan.
Contohnya
Input Output
[4,1,2,3,6,5] [1,3,5] or [1,2,3]
[5,4,2,-1,-2,-4,-4] [5,2,-1,-4]
[1,2,1,3,1,4,1,5,1] [1,1,1,1,1] or [1,2,3,4,5]
[1] [1]
Beberapa kasus uji lagi:
Length: 25
Input: [-9,0,5,15,-1,4,17,-3,20,13,15,9,0,-6,11,17,17,9,26,11,5,11,3,16,25]
Output: [15,13,11,9] or [17,13,9,5]
Length: 50
Input: [35,7,37,6,6,33,17,33,38,30,38,12,37,49,44,5,19,19,35,30,40,19,11,5,39,11,20,28,12,33,25,8,40,6,15,12,27,5,21,6,6,40,15,31,49,22,35,38,22,33]
Output: [6,6,6,6,6] or [39,33,27,21,15]
Length: 100
Input: [6,69,5,8,53,10,82,82,73,15,66,52,98,65,81,46,44,83,9,14,18,40,84,81,7,40,53,42,66,63,30,44,2,99,17,11,38,20,49,34,96,93,6,74,27,43,55,95,42,99,31,71,67,54,70,67,18,13,100,18,4,57,89,67,20,37,47,99,16,86,65,38,20,43,49,13,59,23,39,59,26,30,62,27,83,99,74,35,59,11,91,88,82,27,60,3,43,32,17,18]
Output: [6,18,30,42,54] or [8,14,20,26,32] or [46,42,38,34,30] or [83,63,43,23,3] or [14,17,20,23,26] or [7,17,27,37,47] or [71,54,37,20,3]
Latar Belakang
Saya mendapat ide ini ketika saya mengingat Green-Tao-Theorem dari 2004, yang menyatakan bahwa deret bilangan prima berisi deret aritmatika hingga yang panjangnya sewenang-wenang.
diff
memberikan array kosong yang tidak bisa dinegasikan.Python 2,
1241159897 byteSangat lambat dan intensif memori. Uji di Ideone .
Versi alternatif, 98 byte
Ini menyelesaikan semua kasus uji secara instan. Uji di Ideone .
sumber
Pyth checkout 8593c76, 24 Maret , 10 byte
Ini persis sama dengan jawaban Doorknob, kecuali bahwa kembali pada bulan Maret, ada fungsi 2 byte (
q ... )
) yang memeriksa apakah semua elemen daftar adalah sama, yang sama dengan!P{
, mana yang terbaik yang dapat Anda lakukan saat ini.sumber
JavaScript (ES6), 157 byte
Hampir 20 kali lebih lama dari jawaban Jelly ... Tidak dikumpulkan:
sumber