C++ Academy

🧠Задача о максимальной сумме подмассива (алгоритм Кадане) С++

Дан целочисленный массив, найдите в нем непрерывный подмассив с наибольшей суммой.

Например:

Input:  {-2, 1, -3, 4, -1, 2, 1, -5, 4}
 
Output: Subarray with the largest sum is {4, -1, 2, 1} with sum 6.

Мы можем легко решить эту задачу за линейное время, используя Алгоритм Кадане.
Идея состоит в том, чтобы поддерживать максимальный (с положительной суммой) подмассив, “заканчивающийся” на каждом индексе данного массива. Этот подмассив либо пуст (в этом случае его сумма равна нулю), либо состоит на один элемент больше, чем максимальный подмассив, оканчивающийся на предыдущем индексе.

Алгоритм может быть реализован следующим образом на C++:

#include <iostream>
#include <vector>
using namespace std;
 
// Функция для нахождения максимальной суммы непрерывного подмассива
// в заданном целочисленном массиве
int kadane(vector<int> const &arr)
{
    // сохраняет максимальный суммарный подмассив, найденный на данный момент
    int max_so_far = 0;
 
    // сохраняет максимальную сумму подмассива, заканчивающегося на текущей позиции
    int max_ending_here = 0;
 
    // обход заданного массива
    for (int i = 0; i < arr.size(); i++)
    {
        // обновить максимальную сумму подмассива, "заканчивающегося" на индексе "i" (путем добавления
        // текущий элемент до максимальной суммы, заканчивающейся на предыдущем индексе 'i-1')
        max_ending_here = max_ending_here + arr[i];
 
        // если максимальная сумма отрицательна, устанавливаем ее в 0 (что представляет
        // пустой подмассив)
        max_ending_here = max(max_ending_here, 0);
 
        // обновить результат, если текущая сумма подмассива окажется больше
        max_so_far = max(max_so_far, max_ending_here);
    }
 
    return max_so_far;
}
 
int main()
{
    vector<int> arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
 
    cout << "The maximum sum of a contiguous subarray is " << kadane(arr);
 
    return 0;
}

результат:

The maximum sum of a contiguous subarray is 6

Временная сложность приведенного выше решения равна O(n) и не требует дополнительного места, где n это размер ввода.

Приведенный выше код не обрабатывает случай, когда все элементы массива отрицательные. Если массив содержит все отрицательные значения, ответом является максимальный элемент. Мы можем легко разместить эту проверку перед тем, как продолжить алгоритм. Реализацию можно увидеть ниже на C++:

Продолжение

@cpluspluc

❤7👍6🔥3🍌1

2.87K views12:53