Оптимальный «правильный» подмассив

Условие

Вводится массив из положительных целых чисел. Подмножество элементов этого массива считается «правильным», если каждый его элемент не превышает суммы любых двух остальных элементов из того же подмножества. Необходимо найти наибольшую возможную сумму элементов «правильного» подмножества, образованного из исходных чисел. Заметьте, что любые подмножества, состоящие из одного или двух элементов, автоматически удовлетворяют условию.

Пример 1: [1, 7, 3, 15, 2, 5, 2, 1, 4] → 22 (подмножество {7, 15}) Неправильный пример: [1, 7, 15], потому что 1 + 7 < 15. Примеры правильных подмножеств: [1, 2, 1] со суммой 4 или [3, 5, 4, 7] со суммой 19.

Пример 2: [3, 3, 3, 1, 3, 7, 1] → 12 (подмножество {3, 3, 3, 3})

Ответ

После сортировки достаточно искать лучший непрерывный отрезок: его максимум должен быть не больше суммы двух минимумов. Подмножества размера один и два допустимы без проверки.

Пусть b — отсортированный массив. Для выбранных двух минимумов можно добавить все промежуточные числа до максимума: условие не ухудшится, а сумма вырастет, поскольку числа положительные. Поэтому используем окно и текущую сумму.

def best_sum(values):
    b = sorted(values)
    left = total = best = 0
    for right, value in enumerate(b):
        total += value
        while right - left + 1 >= 3 and b[left] + b[left + 1] < value:
            total -= b[left]
            left += 1
        best = max(best, total)
    return best

Время O(n log n) из-за сортировки, последующий проход O(n). Для примеров получаются 22 и 12. Несмотря на заголовок, условие говорит о подмножестве: порядок исходного массива не ограничивает выбор.