Задача о максимальной сумме подмассива (алгоритм Кадане) на 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:

import java.util.Arrays;
 
class Main
{
    // Функция для нахождения максимальной суммы непрерывного подмассива
    // в заданном целочисленном массиве
    public static int kadane(int[] arr)
    {
        // находим максимальный элемент в заданном массиве
        int max = Arrays.stream(arr).max().getAsInt();
 
        // если массив содержит все отрицательные значения, вернуть максимальный элемент
        if (max < 0) {
            return max;
        }
 
        // сохраняет максимальный суммарный подмассив, найденный на данный момент
        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 = { -8, -3, -6, -2, -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 -2

Этот подход требует двух обходов входного массива. Мы можем легко модифицировать основной алгоритм, чтобы он обрабатывал и отрицательные целые числа. Алгоритм может быть реализован следующим образом на Java:

class Main
{
    // Функция для нахождения максимальной суммы непрерывного подмассива
    // в заданном целочисленном массиве (также обрабатывает отрицательные числа)
    public static int kadaneNeg(int[] arr)
    {
        // сохраняет максимальный суммарный подмассив, найденный на данный момент
        int maxSoFar = Integer.MIN_VALUE;
 
        // сохраняет максимальную сумму подмассива, заканчивающегося на текущей позиции
        int maxEndingHere = 0;
 
        // обход заданного массива
        for (int i: arr)
        {
            // обновить максимальную сумму подмассива, "заканчивающегося" на индексе "i" (путем добавления
            // текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе)
            maxEndingHere = maxEndingHere + i;
 
            // максимальная сумма должна быть больше текущего элемента
            maxEndingHere = Integer.max(maxEndingHere, i);
 
            // обновить результат, если текущая сумма подмассива окажется больше
            maxSoFar = Integer.max(maxSoFar, maxEndingHere);
        }
 
        return maxSoFar;
    }
 
    public static void main(String[] args)
    {
        int[] arr = { -8, -3, -6, -2, -5, -4 };
 
        System.out.println("The maximum sum of a contiguous subarray is " +
                kadaneNeg(arr));
    }
}

результат:

The maximum sum of a contiguous subarray is -2

Из-за того, как этот алгоритм использует оптимальные основания (максимальный подмассив, заканчивающийся в каждой позиции, вычисляется просто из связанной, но меньшей и перекрывающейся подзадачи: максимальный подмассив, заканчивающийся в предыдущей позиции), этот алгоритм можно рассматривать как простой пример динамическое программирование.

Источник