@exother: pamięć O(1) już jest (chyba że tablica wejściowa też się liczy) xd

@NotABigFan:
Dla kolejnych elementów tablicy robimy tak:
- jeśli tab[i] <= 0, to nic nie robimy (traktuję takie miejsca jako "puste")
- w p.p. bierzemy x = tab[i] i dalej
-- jeśli x > większe od rozmiaru tablicy, to je "usuwam", tzn. robię tab[i] = 0
-- w p.p. wrzucam x w tab[x], czyli chciałbym, żeby każdemu odpowiadało jego miejsce w tablicy, a tab[i] czyszczę (ustawiamPokaż całość

@NotABigFan: Ogólnie powinno działać coś takiego: lecimy po kolei i dla każdej i-tej pozycji trzymamy maksymalną sumę, którą do tej pory udało się osiągnąć i teraz mamy dwie opcje: bierzemy i-tą liczbę albo nie, jeżeli bierzemy to aktualnie największą sumą jest wartość i-tej liczby + największa suma i-2, jeżeli nie to i-1 i z tych dwóch wartości bierzemy maxa. To puszczamy od i=2, ustawiamy max sumę dla i=0 i i=1Pokaż całość

@NotABigFan: https://ideone.com/QGXBDp coś w ten deseń

@NotABigFan:

//helper
const addNode = (value, tail) => ({value,Pokaż całość

@NotABigFan: nie czytałem komentarzy. Dwa wskaźniki, wyprzedź ten z krótszej listy o różnice długości list. Przesuwaj wskaźniki, jak są równe to masz ten węzeł którego szukałeś.

@NotABigFan: ['G', 'B', 'R', 'R', 'B', 'R', 'G'].sort().reverse();

Pokaż spoiler

@NotABigFan: Bierzemy dwa wskaźniki: oba ustawiamy na początek listy, ew. jeśli jest tam prefiks składający się z R, to przesuwamy oba do momentu zakończenia listy albo znalezienia nie-R.

Jednym wskaźnikiem idziemy do przodu do momentu znalezienia R - wtedy swapujemy zawartość spod obu wskaźników i przesuwamy +1 ten, który był zostawiony na początku listy. W końcu dolecimy do końca listy, uzyskując w ten sposób prefiks składający sięPokaż całość

@NotABigFan:

const car = f => f((a, b) => a);
const cdr = f => f((a, b) => b);

@nesti32: def car(pair): return pair(lambda x, y: x)

@NotABigFan: Utrzymywać pomocniczą "kolejkę" elementów z obserwowanego okienka w taki sposób, że elementy w tej kolejce są w porządku nierosnącym. Tzn. elementem kolejki jest para (indeks, wartość), kolejne elementy są w stronę rosnących indeksów i malejących wartości. Taka kolejka ma maksymalnie k elementów. Może mieć mniej, jeśli obserwowane okienko nie jest złożone z elementów nierosnących, tylko ma ekstrema.

Mając taką pomocniczą strukturę, max z okienka to wartość pierwszego elementu kolejki.Pokaż całość

@NotABigFan: Zwizualizuj sobie tę kolejkę jako np. listę wskaźnikową. Max jest z lewej strony. Jak wywalisz maksymalny element, to drugi masz zaraz obok i nie musisz już niczego przestawiać (dzięki niezmiennikowi). O(1) operacja.

Jak pojawia się nowy element, to dla zachowania niezmiennika być może musisz coś wywalić z prawej strony. Wywalenie jednego elementu kosztuje O(1), potem wstawienie O(1). Łącznie masz max. n wstawień i usunięć, więc amortyzuje się do O(n).

@WhiskyRomeo: ale pamięć Twojego dicta w pesymistycznej wersji jest proporcjonalna do rozmiaru tablicy i równa O((n-1)/3) czyli O(n) - liniowa.

@NotABigFan: "xor" ale na systemie trójkowym, nie binarnym

3 0010 0010
1 0001 0011
4 0011 0022
1Pokaż całość