Решение задачи

Алгоритм решения задачи:

1) Если мы отсортируем все числа по buckets, проиндексированным по этим числам, это, по сути, попросит вас повторно взять bucket, отказываясь от двух buckets рядом с ним. (диапазон этих чисел [1, 10000])

2) Оптимальный конечный результат можно получить, постоянно обновляя 2 переменные skip_i, take_i, что означает:

skip_i : лучший результат для подзадачи первых (i+1) buckets от 0 до i, при этом вы пропускаете i-й bucket.

take_i : лучший результат для подзадачи первых (i+1) buckets от 0 до i, пока вы берете i-ую buckets.

3) Формула ДП:

take[i] = skip[i-1] + values[i];

skip[i] = Math.max(skip[i-1], take[i-1]);

take[i] может быть получен только из: если вы пропустили [i-1]-е bucket и взяли bucket[i].

skip[i] through, может быть получено из take[i-1] или skip[i-1], в зависимости от того, что больше