算法分治最大子数组

Question

一家 IT 公司想要对收入和支出进行分析 在n个月的时间内。该信息在列表 A[1] 中给出。 。 。 , A[n] 与 整数值。在第 i 个月，公司出现了与某人相对应的赤字或盈余 位置 A[i] 中的正整数或负整数。目标是找到一个连续的区间 公司利润总额最高的月份。以下是三个例子： (aʹ) A = [30, −50, 20, −50]，其中总利润最大的区间为从月开始 1 直到第 1 个月，利润为 30， (bʹ) A = [30, −5, 20, −50]，其中总利润最大的区间是从月份开始 1 到第 3 个月，总利润等于 45， (cʹ) A = [30, −50, 20, −5, 40]，其中总利润最大的区间为 第 3 个月到第 5 个月的利润总额等于 55。 设计高效的分而治之算法。到 分析正确性和复杂性，描述并解决逆向问题 表示算法时间复杂度的位关系。

我除以 /2 直到每个数组只有一个元素。然后我找到最大值，但我不知道如何找到月份数。

Answer 1

对于每个区间，您可以计算当前区间的前缀的最大和、当前区间的后缀的最大和以及当前区间包含的子数组的总体最大和。

较大区间的总体最佳结果要么完全包含在左侧部分（求解左侧区间的总体最佳结果），要么完全包含在右侧部分（求解右侧区间的总体最佳结果），或者跨越两半（即左侧最大后缀和与右侧最大前缀和之和）。

C++ 示例实现：

#include <algorithm>
#include <span>
#include <numeric>
struct Result {
    int prefixBest, suffixBest, overallBest;
};
Result solve(std::span<int> nums) {
    if (nums.size() == 1) return {nums[0], nums[0], nums[0]};
    auto leftPart = nums.subspan(0, nums.size() / 2), rightPart = nums.subspan(nums.size() / 2);
    auto leftRes = solve(leftPart), rightRes = solve(rightPart);
    return {
        leftRes.prefixBest + (leftRes.prefixBest == std::accumulate(leftPart.begin(), leftPart.end(), 0)) * std::max(rightRes.prefixBest, 0),
        rightRes.suffixBest + (rightRes.suffixBest == std::accumulate(rightPart.begin(), rightPart.end(), 0)) * std::max(leftRes.suffixBest, 0),
        std::max({leftRes.overallBest, rightRes.overallBest, leftRes.suffixBest + rightRes.prefixBest})
    };
}
#include <iostream>
#include <vector>
int main() {
    std::vector v{30, -50, 20, -5, 40};
    std::cout << solve(v).overallBest; // 55
}

请注意，使用分治法比使用前缀和或 Kadane 算法的解决方案慢 (

O(N log N)

)，这两种算法都是

O(N)

。