Задача о максимальном подмассиве — это классическая алгоритмическая задача, которая включает в себя поиск в заданном массиве целых чисел непрерывного подмассива, имеющего наибольшую сумму. В этой статье блога мы рассмотрим различные методы эффективного решения этой проблемы с помощью C++. Мы углубимся в различные подходы, включая динамическое программирование, алгоритм Кадане, методы «разделяй и властвуй», скользящее окно и методы суммирования префиксов. Итак, начнём!

Метод 1: динамическое программирование
Динамическое программирование — это популярный метод решения задач оптимизации путем разбиения их на перекрывающиеся подзадачи. Для задачи о максимальном подмассиве мы можем использовать динамическое программирование, чтобы найти подмассив максимальной суммы, заканчивающийся в каждой позиции массива. Конечным результатом будет максимальная сумма среди всех этих подмассивов. Вот код:

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int maxSum = nums[0];
    int currSum = nums[0];

    for (int i = 1; i < n; i++) {
        currSum = max(nums[i], currSum + nums[i]);
        maxSum = max(maxSum, currSum);
    }

    return maxSum;
}

Метод 2: алгоритм Кадане
Алгоритм Кадане представляет собой оптимизированную версию подхода динамического программирования. Он поддерживает две переменные, maxSumи currSum, которые представляют подмассив максимальной суммы, заканчивающийся текущей позицией и текущей суммой соответственно. Алгоритм перебирает массив, обновляя эти переменные по мере необходимости. Вот код:

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int maxSum = nums[0];
    int currSum = nums[0];

    for (int i = 1; i < n; i++) {
        currSum = max(nums[i], currSum + nums[i]);
        maxSum = max(maxSum, currSum);
    }

    return maxSum;
}

Метод 3: разделяй и властвуй
Подход «разделяй и властвуй» разбивает массив на более мелкие подмассивы, решает проблему рекурсивно для каждого подмассива и объединяет результаты для поиска максимального подмассива. Этот метод имеет временную сложность O(n log n). Вот код:

int maxSubArray(vector<int>& nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }

    int mid = left + (right - left) / 2;
    int leftMax = maxSubArray(nums, left, mid);
    int rightMax = maxSubArray(nums, mid + 1, right);
    int crossingMax = findMaxCrossingSubarray(nums, left, mid, right);

    return max(max(leftMax, rightMax), crossingMax);
}
int findMaxCrossingSubarray(vector<int>& nums, int left, int mid, int right) {
    int leftSum = INT_MIN;
    int sum = 0;

    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = max(leftSum, sum);
    }

    int rightSum = INT_MIN;
    sum = 0;

    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = max(rightSum, sum);
    }

    return leftSum + rightSum;
}

Метод 4: скользящее окно
Техника скользящего окна предполагает сохранение окна переменного размера во время итерации по массиву. Мы сдвигаем окно слева направо, обновляя подмассив максимальной суммы по мере продвижения. Этот метод имеет временную сложность O(n). Вот код:

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int maxSum = nums[0];
    int currSum = nums[0];

    for (int i = 1; i < n; i++) {
        if (currSum < 0) {
            currSum = nums[i];
        } else {
            currSum += nums[i];
        }

        maxSum = max(maxSum, currSum);
    }

    return maxSum;
}

Метод 5: Префиксная сумма
Техника префиксной суммы включает предварительное вычисление совокупной суммы элементов массива. Вычитая значения суммы префикса, мы можем найти подмассив максимальной суммы. Этот метод имеет временную сложность O(n). Вот код:

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int maxSum = nums[0];
    intcurrSum = nums[0];
    int minSum = 0;
    int prefixSum = nums[0];

    for (int i = 1; i < n; i++) {
        prefixSum += nums[i];
        maxSum = max(maxSum, prefixSum - minSum);
        minSum = min(minSum, prefixSum);
    }

    return maxSum;
}

В этой статье мы рассмотрели различные методы решения проблемы максимального подмассива в C++. Мы обсудили динамическое программирование, алгоритм Кадане, методы «разделяй и властвуй», скользящее окно и методы суммирования префиксов. Каждый метод имеет свои преимущества и может использоваться в зависимости от требований задачи. Понимая эти различные подходы, вы будете хорошо подготовлены к эффективному решению проблемы максимального подмассива.