Urutan berikutnya adalah urutan yang dapat diturunkan dari urutan lain dengan menghapus beberapa elemen tanpa mengubah urutan elemen yang tersisa. Sebuah urutan yang meningkat secara ketat adalah urutan di mana setiap elemen lebih besar dari yang sebelumnya.
Urutan peningkatan urutan terberat adalah peningkatan urutan tertinggi yang memiliki jumlah elemen terbesar.
Menerapkan program atau fungsi dalam bahasa pilihan Anda yang menemukan jumlah elemen dari peningkatan berikutnya terberat dari daftar bilangan bulat non-negatif yang diberikan.
Contoh:
[] -> 0 ([])
[3] -> 3 ([3])
[3, 2, 1] -> 3 ([3])
[3, 2, 5, 6] -> 14 ([3, 5, 6])
[9, 3, 2, 1, 4] -> 9 ([9])
[3, 4, 1, 4, 1] -> 7 ([3, 4])
[9, 1, 2, 3, 4] -> 10 ([1, 2, 3, 4])
[1, 2, 4, 3, 4] -> 10 ([1, 2, 3, 4])
[9, 1, 2, 3, 4, 5, 10] -> 25 ([1, 2, 3, 4, 5, 10])
[3, 2, 1, 2, 3] -> 6 ([1, 2, 3])
Perhatikan bahwa Anda hanya perlu memberikan jumlah elemen dari peningkatan yang terberat, bukan yang berikutnya.
Kode tercepat asimptotik menang, dengan ukuran kode lebih kecil dalam byte sebagai tiebreak.
Jawaban:
javascript (ES6)
O(n log n)
253 karakterini menggunakan pohon fenwick (pohon fenwick maksimum) untuk menemukan maksimum dari urutan-urutan tertentu.
pada dasarnya, dalam array yang mendasari tipe data, setiap tempat dicocokkan dengan elemen dari daftar input, dalam urutan yang sama. pohon fenwick diinisialisasi dengan 0 di mana-mana.
dari yang terkecil hingga yang terbesar, kami mengambil elemen dari daftar input, dan mencari maksimum elemen ke kiri. mereka adalah elemen yang mungkin sebelum ini di urutan berikutnya, karena mereka berada di sebelah kiri dalam urutan input, dan lebih kecil, karena mereka memasuki pohon sebelumnya.
jadi maksimum yang kami temukan adalah urutan terberat yang bisa sampai ke elemen ini, dan jadi kami menambah bobot elemen ini, dan mengaturnya di pohon.
maka, kita cukup mengembalikan maksimal seluruh pohon tersebut hasilnya.
diuji pada firefox
sumber
Python, O (n log n)
Saya tidak bermain golf ini, karena saya bersaing terutama pada sisi kode tercepat. Solusi saya adalah
heaviest_subseq
fungsinya, dan test harness juga disertakan di bagian bawah.Analisis runtime:
Setiap elemen memiliki posisi penyisipan yang dicari sekali, dimasukkan sekali, dan mungkin dihapus sekali, di samping jumlah pencarian nilai yang konstan per loop. Karena saya menggunakan paket bisect bawaan dan paket blist , masing-masing operasi itu
O(log n)
. Jadi, keseluruhan runtime adalahO(n log n)
.Program ini bekerja dengan mempertahankan daftar yang disortir dari kemungkinan kenaikan berikutnya, diwakili sebagai tuple dari nilai akhir dan jumlah urutan. Urutan berikutnya yang meningkat ada di daftar itu jika tidak ada urutan lain yang ditemukan sejauh ini yang nilai akhirnya lebih kecil dan jumlah setidaknya sama besar. Ini dipertahankan dalam urutan peningkatan nilai akhir, dan tentu juga dalam urutan peningkatan jumlah. Properti ini dikelola dengan memeriksa penerus setiap urutan yang baru ditemukan, dan menghapusnya jika jumlahnya tidak cukup besar, dan mengulangi sampai urutan dengan jumlah yang lebih besar tercapai, atau akhir daftar tercapai.
sumber
Python, O (n log n)
Saya menggunakan indeks transformasi dan struktur data yang bagus (pohon indeks biner) untuk meremehkan masalah.
Pohon indeks biner dapat melakukan dua operasi dalam log (n): meningkatkan nilai pada indeks i dan mendapatkan nilai maksimum dalam [0, i). Kami menginisialisasi setiap nilai di pohon menjadi 0. Kami indeks pohon menggunakan peringkat elemen, bukan indeks mereka. Ini berarti bahwa jika kita mengindeks pohon pada indeks i, semua elemen [0, i) adalah elemen yang lebih kecil dari elemen dengan peringkat i. Ini berarti bahwa kami mendapatkan maksimum dari [0, i), menambahkan nilai saat ini, dan memperbaruinya di i. Satu-satunya masalah adalah bahwa ini akan mencakup nilai yang kurang dari nilai saat ini, tetapi datang kemudian dalam urutan. Tetapi karena kita bergerak melalui urutan dari kiri ke kanan dan kita menginisialisasi semua nilai di pohon ke 0, mereka akan memiliki nilai 0 dan dengan demikian tidak mempengaruhi maksimum.
sumber
Python 2 -
O(n^2)
- 114 bytesumber
C ++ -
O(n log n)
- 261 byteHarus diperbaiki sekarang:
sumber
auto S=set<pair<I,I>>();
lebih panjang dari sekadarset<pair<I,I>> S;
.#define I int
lebih panjang dariusing I=int;
. Tidak perlu menetapkann
apa pun, Anda dapat menggantinyaauto n=*prev(S.lower_bound({w,-1}));I y=n.second
denganI y=prev(S.lower_bound({w,-1}))->second+w;
.S
sangat berbelit-belit, Anda bisa meninggalkan insert dan menggunakanstd::set<std::pair<int,int>>S{{-1,0}};
.using namespace std;using I=int;I h(vector<I>l){I W=0;set<pair<I,I>>S{{-1,0}};for(I w:l){I y=prev(S.lower_bound({w,-1}))->second+w;W=max(W,y);S.insert({w,y});}return W;}
std::max
, gunakanW=y>W?y:W;
.Matlab, O ( n 2 n ), 90 byte
Contoh:
sumber
Python, O (2 n ), 91 byte
Ini lebih untuk bersenang-senang daripada bersaing. Solusi rekursif misterius:
sumber
max(m,l[0])
mengingat itunot(l[0]<m)
adill[0]
, tentu saja?