Максимальная сумма по подмассиву с одним удалением
Источник: https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/
Дан массив целых чисел, вернуть сумму по не пустому подмассиву (состоит из смежных элементов исходного массива), который можно получить удалением не более одного элемента массива. Другими словами, можно выбрать подмассив и опционально удалить из него один элемент, чтобы получить подмассив с максимальной суммой элементов.
Пример 1:
Дано: arr = [1,-2,0,3] Результат: 4 Пояснение: Мы можем взять весь иходный массив [1, -2, 0, 3] и удалить из него -2, и таким образом получим подмассив [1, 0, 3], сумма элементов которого даст максимум по всем возможным подмассивам.
Пример 2:
Дано: arr = [1,-2,-2,3] Результат: 3 Пояснение: Мы просто берем подмассив [3] и он даст максимально возможную сумму по всем подмассивам даже с удалением одного элемента.
Пример 3:
Дано : arr = [-1,-1,-1,-1] Результат: -1 Пояснение: Результата не существует. Мы можем выбрать подмассив [-1] и удалить из него -1, и мы получим тогда максимальную сумму = 0 (что больше, чем сумма по любому подмассиву), но это будет пустой подмассив, а по условию задачи это недопустимо.
Ограничения:
1 <= arr.length <= 105-104 <= arr[i] <= 104
Идея решения
Это задача похожа на задачу, которую решает алгоритм Кадана. Разница в том, что мы ещё можем и удалить один элемент из найденного подмассива. Но если мы этот элемент удалим из исходного массива, то алгоритм Кадана найдет подмассив без этого удаленного элемента.
Таким образом, решение "в лоб" - перебрать все варианты исходного массива без одного элемента (сначала удалим первый элемент, потом вернем его и удалим второй, и так далее) и к каждому применить алгроритм Кадана.
Однако, создание варианта массива без какого-либо элемента - это досаточно трудоемкая операция. Также массив, кторый использует алгоритм Кадана для сохранения своих подсчётов, тоже во многих случаях будет пересчитываться многократно для своих ячеек на основании одних и тех же данных. Поэтому прибегнем к бинамическому программированию.
Подсчитаем алгоритм Кадана, как обычно, слева направо, создавая при этом массивы локальных максимумов по префиксам исходного массива (как мы это сделали в предыдущей задаче Максимальная сумма в k-конкатенации массива). Затем сделаем "прогон" справа-налево. Результат для алгоритма Кадана будет тот же, а вот локальные максимумы будут отличаться, потому что они будут подсчитаны для суффиксов исходного массива.
Каждый элемент i в массиве префиксов будет подсчитан для исходного массива по индексам от 0 до i. С другой стороны, i-й элемент массива суффиксов подсчитан для элементов i...lenght исходного массива.
И если нам надо сэмулировать ситуацию удаления i-го элемента из исходного массива и подсчёта алгоритма Кадана для модифицированной версии, то достаточно будет просто сложить префикс для элементов 0...i-1 с суффиксом для i+1...length.
Имплементация
int len = arr.length;
// проверяем крайние случаи
if (len == 0) {
return 0;
}
if (len == 1) {
return arr[0];
}
int result = Integer.MIN_VALUE;
// готовим массивы для левого и правого сканирования
int[] left = new int[len];
int[] right = new int[len];
// сканируем сначала слева направо по префиксам массива
// и считаем локальные максимумы
left[0] = arr[0];
for (int i = 1; i < len; i++) {
left[i] = Math.max(arr[i], left[i-1]+arr[i]);
result = Math.max(result, left[i]);
}
// считаем локальные максимумы для суффиксов массива
right[len-1] = arr[len-1];
for (int i = len-2; i >= 0; i--) {
right[i] = Math.max(arr[i], right[i+1]+arr[i]);
}
// симулиуем алгоритм Кадана, когда исключен i-й элемент
for (int i = 1; i < len-1; i++) {
result = Math.max(left[i-1] + right[i+1], result);
}
return result;
}
Комментарии
Отправить комментарий