Максимальная сумма двух непересекающихся подмассивов
Массивы (списки)
Средняя
Дан массив nums и две длины firstLen и secondLen. Выберите два непересекающихся (не обязательно смежных друг с другом) подмассива: один длины firstLen, другой длины secondLen (в любом порядке следования). Верните максимальную суммарную сумму элементов обоих подмассивов.
Переберите все пары стартовых позиций - O(n^2), либо один проход с префиксными суммами: для каждой позиции старта второго окна храните максимальную сумму первого окна среди всех, что заканчиваются раньше - O(n).
Сигнатура функции
max_sum_two_subarrays(nums: list[int], first_len: int, second_len: int) -> int
Примеры
| Вход | Ожидаемый результат |
|---|
| [[0, 6, 5, 2, 2, 5, 1, 9, 4], 1, 2] | 20 |
| [[3, 8, 1, 3, 2, 1, 8, 9, 0], 3, 2] | 29 |
1решили
1пытались
100%успешность
Войдите, чтобы решить →