Cześć,
niedawno natknąłem się na zadanie z XII Olimpiady Informatycznej Gimnazjalistów o nazwie "płot". Chodzi w nim o to, że na wejściu podaną mamy liczbę n (1 <= n <= 200 000), a następnie n liczb, z których każda jest nie mniejsza od 1 i nie większa od 10^6. Trzeba usunąć niektóre liczby, tak aby suma pozostałych była jak największa i aby wartości pozostawionych liczb na zmianę rosły i malały.
Np. dla danych wejściowych:
6
7 5 4 6 6 5
rozwiązaniem jest 23, gdyż wystarczy usunąć 4 i jedno 6.
Myślałem nad tym zadaniem godzinę i nie mam żadnego pomysłu. Patrząc na zakres wartości n, wydaję mi się, że rozwiązanie może mieć złożoność około O(n log n), ale nie jestem pewien. Bardzo prosiłbym o nakierowanie na poprawne rozwiązanie.