Kadence 算法：最大和连续子数组

由： 陈莎拉 陈莎拉
Hours 更新

⚡ 智能摘要

Kadane 算法可在线性时间内找到最大和连续子数组。 trac与其扫描每个可能的子数组，不如寻找运行最大值。这种经典的动态规划技巧在股票、金融和信号问题中发挥着重要作用。

  • 🎯 问题定义： 连续子数组是一系列连续的元素；目标是混合正负数组中算术和最大的子数组。
  • 🐢 蛮力： 两个嵌套循环在 O(N²) 时间内评估每个开始和结束索引，并使用开始和结束标记打印获胜窗口。
  • ⚡ 卡丹的见解： 当当前元素大于累加器时，重置运行总和，keeping 只选择最合适的前缀，它最终还能发展成答案。
  • 🧭 示例： 通过对包含负数的数组进行简单的遍历，可以看到 max_sum 和 current_sum 如何逐步演变，直到达到真正的最大值。
  • 💻 语言覆盖范围： 以上皆是 C++ 和 Python 简单方法和 Kadane 算法的实现证明了时间复杂度从 O(N²) 过渡到 O(N)。
  • 📊 复杂： Kadane 算法的运行时间为 O(N)，额外空间为 O(1)，在大输入数组上显著优于暴力基线算法。
阅读更多

Kadane算法最大和连续子数组

什么是最大和连续子数组？

子数组是数组的连续部分。它可以是数组的单个元素，也可以是数组的某个部分。最大和连续子数组是指具有最大和值的子数组。

例如，考虑数组 {-10, 5, 1, 6, -9, 2, -7, 3, -5}。它的子数组可以是 {-10, 5, 1, 6}、{5, 1, 6} 或 {2, -7, 3, -5}，依此类推。但是，{5, 1, 6, 3} 不能作为子数组，因为其中的元素不是连续的。

最大和连续子数组

如果你仔细观察，会发现所有子数组中，高亮显示的子数组 {5, 1, 6} 的总和值最大：

最大和连续子数组突出显示

子数组 {5, 1, 6} 的和为 12，这是上述数组所有可能子数组中的最大和。因此，对于该数组，和最大的连续子数组是 {5, 1, 6}。

求解最大和连续子数组的简单方法

这道题的简单解决方法就是用两次循环找出所有子数组，计算和，然后找到它的最大值。

以下是寻找最大和连续子数组的简单方法的流程图。这是一种穷举法，因为我们需要遍历所有可能的子数组。

解决最大和的简单方法

以下是执行此操作的简单步骤。

步骤1） 初始化 最大和 最小整数值并设置 开始 和 end 归零。

步骤2） 让 i 和 j 是数组索引，其中 j 大于或等于 i; i 标记子数组的起始位置和 j 它的终结。

步骤3） 当前总和 保存累计总和。每次更新后，检查是否 当前总和 大于 最大和.

步骤4） If 当前总和 如果更大，则替换 最大和 用它。

步骤5） 日期 j 到达数组末尾时，递增 i 并重置 当前总和 到0。

步骤6） 重复直到 i 到达数组末尾。 最大和 然后保存最大的子数组和。

昵称 Code 简易方法

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum

C++ 简单方法的实施

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
    int max_sum = -1e9;
    int begin = 0;
    int end = 0;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += array[j];
            if (max_sum < current_sum) {
                max_sum = current_sum;
                begin = i;
                end = j;
            }
        }
    }
    cout << "largest sum is " << max_sum << endl;
    cout << "largest sum contiguous subarray: ";
    for (int i = begin; i <= end; i++) {
        cout << array[i] << "\t";
    }
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

输出：

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python 简单方法的实施

def maximumSubarraySum(numbers):
    max_sum, begin, end = -1e9, 0, 0
    for i in range(len(numbers)):
        current_sum = 0
        for j in range(i, len(numbers)):
            current_sum += numbers[j]
            if max_sum < current_sum:
                max_sum = current_sum
                begin, end = i, j
    print("largest sum is ", max_sum)
    print("largest sum contiguous subarray: ", end='')
    for i in range(begin, end + 1):
        print(numbers[i], end='\t')

numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5]
maximumSubarraySum(numbers)

输出：

largest sum is 12
largest sum contiguous subarray: 5      1       6

相关文章

Kadane算法寻找最大和连续子数组

Kadane 算法是一种动态规划方法，它使用单个循环而不是两个循环。它可以处理包含正数和负数的混合数组，只要至少有一个值是非负数即可。

我们只需要两个变量就能找到最大的连续子数组和。流程图如下：

Kadane算法求最大和

以下是 Kadane 算法的步骤：

步骤1） 创建两个变量， 当前总和 和 最大和.

当前总和 保留以特定数组索引结尾的最大和，而 最大和 存储目前为止观察到的最大总和值。

步骤2） 将每个数组元素添加到 当前总和然后检查以下两个条件：

  • If 当前总和 如果小于当前元素，则 当前总和 成为当前元素。
  • If 最大和 小于 当前总和， 然后 最大和 成为 当前总和.

步骤3） 对整个数组重复上一步后， 最大和 包含最大的连续子数组总和。

Kadane 算法的示例

我们用一个小数组演示 Kadane 算法，并逐步讲解如何找到最大和连续子数组。

假设给定的数组如下所示：

Kadane 算法的示例

以下是卡丹算法的步骤：

步骤1） 创建两个变量， 当前总和 和 最大和将 INT_MIN 赋值给 最大和 和零到 当前总和其中，INT_MIN 表示最小整数值。

步骤2） 索引 0 处的值为 4。所以， 当前总和 = 0 + 4 = 4。因为 当前总和 大于 最大和, 最大和 变成 4。

Kadane算法步骤2示例

步骤3） 索引 1 处的值为 -2。所以， 当前总和 = 4 + (-2) = 2。

这次 当前总和 小于 最大和因此，其价值 最大和 未更新。

Kadane算法步骤3示例

步骤4） 下一个值是 1。将其加到 当前总和 给出3。因为 最大和 （4）仍然大于 当前总和, 最大和 未更新。

Kadane算法步骤4示例

步骤5） 索引为 3 时，值为 3。递增 当前总和 乘以 3 得到 当前总和 = 6。

Kadane算法步骤5示例

在这种情况下， 最大和 小于 当前总和，所以 最大和 已更新为以下值： 当前总和.

步骤6） 数组的最后一个元素是 -1。将其加到 当前总和 结果是 5，小于 最大和。 所以， 最大和 剩余6。

Kadane算法步骤6示例

由于我们已经遍历到了数组的末尾，算法也到此结束。现在， 最大和 包含最大和，即 6。子数组为 {4, -2, 1, 3}。

昵称 Code 卡丹算法

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++ Kadane 算法的实现

#include <iostream>
using namespace std;
void kadane(int array[], int n) {
    int current_sum = 0;
    int max_sum = -1e9;
    // -1e9 means -1,000,000,000
    for (int i = 0; i < n; i++) {
        current_sum += array[i];
        if (max_sum < current_sum) {
            max_sum = current_sum;
        }
        if (current_sum < array[i]) {
            current_sum = array[i];
        }
    }
    cout << "largest sum is " << max_sum << endl;
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    kadane(array, sizeof(array) / sizeof(array[0]));
}

输出：

largest sum is 12

Python Kadane 算法的实现

def kadane(numbers):
    current_sum = 0
    max_sum = -1e9
    for i in range(len(numbers)):
        current_sum += numbers[i]
        if max_sum < current_sum:
            max_sum = current_sum
        if current_sum < numbers[i]:
            current_sum = numbers[i]
    print("largest sum is ", max_sum)

kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])

输出：

largest sum is 12

最大和连续子阵列的复杂度分析

这种简单的方法使用两个循环来计算每个可能的子数组和，并找到最大的和。这是一种暴力搜索方法；每个循环都会运行到数组末尾。 排列，给 O(N²) 时间。

Kadane 算法仅使用一个循环，时间复杂度为 O(N)，空间复杂度为 O(1)。对于一个包含 100 个元素的数组，简单的算法需要执行 100 × 100 = 10,000 次运算，而 Kadane 算法仅需 100 次运算——对于大型输入，速度提升非常显著。

常见问题

Kadane算法是时间序列数据人工智能特征工程、异常窗口检测和奖励共享的基础。ping 在强化学习中，帮助ping 模型能够识别噪声信号中最强的正和区间。

是的。GitHub Copilot 和 GPT 都能可靠地输出 Kadane 算法。 Python, C++和 Java包括返回获胜子数组的起始索引和结束索引的变体。

Kadane 算法的时间复杂度为 O(N)，辅助空间复杂度为 O(1)，因为它只进行一次遍历。 trac仅代表累计金额和目前为止的最佳价值。

将 max_sum 初始化为第一个元素或负无穷大，而不是零。然后，算法返回最小负数元素，即正确答案。

常见用途包括股票买卖利润窗口、图像边缘总和、基因组评分区间以及金融风险分析，其中最佳连续回报窗口最为重要。

Trac当 current_sum 重置为当前元素时，使用 ka 作为临时起始索引。当 max_sum 更新时，捕获起始和结束索引，以便在最后对结果子数组进行切片。

分治法通过合并左和、右和以及交叉和，在 O(N log N) 的时间内求解最大子数组。Kadane 算法速度更快，时间复杂度为 O(N)，且更易于编写代码。

是的。Kadane 问题是一个典型的动态规划示例，其状态复杂度为 O(1)，其中索引为 i 的每个新最大值都取决于索引为 i 减 1 的最大值加上当前元素。

总结一下这篇文章：