83 подписчика
Задача о максимальной сумме подмассива (алгоритм Кадане) на Java
Дан целочисленный массив, найдите в нем непрерывный подмассив с наибольшей суммой.
Например:
Input: {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Output: Subarray with the largest sum is {4, -1, 2, 1} with sum 6.
Мы можем легко решить эту задачу за линейное время, используя Алгоритм Кадане.
Идея состоит в том, чтобы поддерживать максимальный (с положительной суммой) подмассив, “заканчивающийся” на каждом индексе данного массива. Этот подмассив либо пуст (в этом случае его сумма равна нулю), либо состоит на один элемент больше, чем максимальный подмассив, оканчивающийся на предыдущем индексе.
Алгоритм может быть реализован следующим образом на Java:
class Main
{
// Функция для нахождения максимальной суммы непрерывного подмассива
// в заданном целочисленном массиве
public static int kadane(int[] arr)
{
// сохраняет максимальный суммарный подмассив, найденный на данный момент
int maxSoFar = 0;
// сохраняет максимальную сумму подмассива, заканчивающегося на текущей позиции
int maxEndingHere = 0;
// обход заданного массива
for (int i: arr)
{
// обновить максимальную сумму подмассива, "заканчивающегося" на индексе "i" (путем добавления
// текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе 'i-1')
maxEndingHere = maxEndingHere + i;
// если максимальная сумма отрицательна, устанавливаем ее в 0 (что представляет
// пустой подмассив)
maxEndingHere = Integer.max(maxEndingHere, 0);
// обновить результат, если текущая сумма подмассива окажется больше
maxSoFar = Integer.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
public static void main(String[] args)
{
int[] arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
System.out.println("The sum of contiguous subarray with the " +
"largest sum is " + kadane(arr));
}
}
результат:
The maximum sum of a contiguous subarray is 6
Временная сложность приведенного выше решения равна O(n) и не требует дополнительного места, где n это размер ввода.
Приведенный выше код не обрабатывает случай, когда все элементы массива отрицательные. Если массив содержит все отрицательные значения, ответом является максимальный элемент. Мы можем легко разместить эту проверку перед тем, как продолжить алгоритм. Реализацию можно увидеть ниже на Java:
1 минута
18 июня 2023
217 читали