Selanjutnya meningkat terberat

9

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.

orlp
sumber
Bagaimana Anda berencana menangani asimtotik yang tak tertandingi? Ada dua variabel penting: panjang urutan, dan ukuran elemen terbesar dalam urutan.
Peter Taylor
@ PeterTaylor Saya memilih panjang urutan sebagai asimptotik. Solusi Anda tidak boleh mengasumsikan terikat pada bilangan bulat, dan khususnya tidak mengulang atau mengalokasikan memori berdasarkan ukuran angka yang terlibat. Anda dimaafkan jika pilihan bahasa Anda telah membatasi bilangan bulat, tetapi Anda tidak boleh menggunakan fakta ini dalam solusi Anda. Apakah itu memuaskan kekhawatiran Anda?
orlp
Sebagian. Secara teori masih mungkin (walaupun mungkin tidak mungkin) bahwa fakta bahwa perbandingan dua bilangan bulat tak terbatas mengambil ukuran yang sebanding dengan log mereka bisa relevan. Anda mungkin ingin mengizinkan operasi dasar (penambahan, perbandingan, mungkin multiplikasi) pada bilangan bulat untuk dianggap sebagai O (1) waktu.
Peter Taylor
@ PeterTaylor Apakah model komputasi transdichotomous cukup spesifik?
orlp
Tampaknya masuk akal.
Peter Taylor

Jawaban:

3

javascript (ES6) O(n log n)253 karakter

function f(l){l=l.map((x,i)=>[x,i+1]).sort((a,b)=>a[0]-b[0]||1)
a=[0]
m=(x,y)=>x>a[y]?x:a[y]
for(t in l)a.push(0)
t|=0
for(j in l){for(i=(r=l[j])[1],x=0;i;i&=i-1)x=m(x,i)
x+=r[0]
for(i=r[1];i<t+2;i+=i&-i)a[i]=m(x,i)}for(i=t+1;i;i&=i-1)x=m(x,i)
return x}

ini 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

haskeller bangga
sumber
4

Python, O (n log n)

Saya tidak bermain golf ini, karena saya bersaing terutama pada sisi kode tercepat. Solusi saya adalah heaviest_subseqfungsinya, dan test harness juga disertakan di bagian bawah.

import bisect
import blist

def heaviest_subseq(in_list):
    best_subseq = blist.blist([(0, 0)])
    for new_elem in in_list:

        insert_loc = bisect.bisect_left(best_subseq, (new_elem, 0))

        best_pred_subseq_val = best_subseq[insert_loc - 1][1]

        new_subseq_val = new_elem + best_pred_subseq_val

        list_len = len(best_subseq)
        num_deleted = 0

        while (num_deleted + insert_loc < list_len
               and best_subseq[insert_loc][1] <= new_subseq_val):
            del best_subseq[insert_loc]
            num_deleted += 1

        best_subseq.insert(insert_loc, (new_elem, new_subseq_val))

    return max(val for key, val in best_subseq)

tests = [eval(line) for line in """[]
[3]
[3, 2, 1]
[3, 2, 5, 6]
[9, 3, 2, 1, 4]
[3, 4, 1, 4, 1]
[9, 1, 2, 3, 4]
[1, 2, 4, 3, 4]
[9, 1, 2, 3, 4, 5, 10]
[3, 2, 1, 2, 3]""".split('\n')]

for test in tests:
    print(test, heaviest_subseq(test))

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 adalah O(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.

isaacg
sumber
Menarik, solusi yang sangat berbeda dari saya .
orlp
2

Python, O (n log n)

Saya menggunakan indeks transformasi dan struktur data yang bagus (pohon indeks biner) untuk meremehkan masalah.

def setmax(a, i, v):
    while i < len(a):
        a[i] = max(a[i], v)
        i |= i + 1

def getmax(a, i):
    r = 0
    while i > 0:
        r = max(r, a[i-1])
        i &= i - 1
    return r

def his(l):
    maxbit = [0] * len(l)
    rank = [0] * len(l)
    for i, j in enumerate(sorted(range(len(l)), key=lambda i: l[i])):
        rank[j] = i

    for i, x in enumerate(l):
        r = rank[i]
        s = getmax(maxbit, r)
        setmax(maxbit, r, x + s)

    return getmax(maxbit, len(l))

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.

orlp
sumber
1

Python 2 - O(n^2)- 114 byte

def h(l):
 w=0;e=[]
 for i in l:
    s=0
    for j,b in e:
     if i>j:s=max(s,b)
    e.append((i,s+i));w=max(w,s+i)
 return w
Tyilo
sumber
1

C ++ - O(n log n)- 261 byte

Harus diperbaiki sekarang:

#include <set>
#include <vector>
int h(std::vector<int>l){int W=0,y;std::set<std::pair<int,int>>S{{-1,0}};for(w:l){auto a=S.lower_bound({w,-1}),b=a;y=prev(a)->second+w;for(;b!=S.end()&&b->second<=y;b++){}a!=b?S.erase(a,b):a;W=y>W?y:W;S.insert({w,y});}return W;}
Tyilo
sumber
auto S=set<pair<I,I>>();lebih panjang dari sekadar set<pair<I,I>> S;. #define I intlebih panjang dari using I=int;. Tidak perlu menetapkan napa pun, Anda dapat menggantinya auto n=*prev(S.lower_bound({w,-1}));I y=n.seconddengan I y=prev(S.lower_bound({w,-1}))->second+w;.
orlp
Oh, dan inisialisasi Ssangat berbelit-belit, Anda bisa meninggalkan insert dan menggunakan std::set<std::pair<int,int>>S{{-1,0}};.
orlp
@ atau terima kasih! Ini menunjukkan bahwa saya tidak menggunakan c ++;)
Tyilo
Berikut ini versi yang jauh lebih pendek (masih membutuhkan set dan vektor termasuk):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;}
orlp
Oh dan buang std::max, gunakan W=y>W?y:W;.
orlp
0

Matlab, O ( n 2 n ), 90 byte

function m=f(x)
m=0;for k=dec2bin(1:2^numel(x)-1)'==49
m=max(m,all(diff(x(k))>0)*x*k);end

Contoh:

>> f([])
ans =
     0
>> f([3])
ans =
     3
>> f([3, 2, 5, 6])
ans =
    14
Luis Mendo
sumber
0

Python, O (2 n ), 91 byte

Ini lebih untuk bersenang-senang daripada bersaing. Solusi rekursif misterius:

h=lambda l,m=0:l and(h(l[1:],m)if l[0]<=m else max(h(l[1:],m),l[0]+h(l[1:],l[0])))or 0
orlp
sumber
1
max(m,l[0])mengingat itu not(l[0]<m)adil l[0], tentu saja?
Peter Taylor
@PeterTaylor Derp.
orlp
Jawaban ini tampaknya bukan penantang yang serius.
pppery