最大和连续子数组

子数组是一个数组的连续部分。 考虑给定的数组 nums; 我们必须找到包含正数和负数的连续数组，返回其总和。

假设数组是

A: [-2, 1, -3, -1, 2, 1, -5, 4]

我们可以在上面的数组中观察到该数组包含负整数和正整数。 上面数组中的索引从 0 到 8 开始。现在的问题是，“哪个连续数组的和最大”。 连续是什么意思？ 这里连续意味着我们在从数组中获取的代码段中没有中断。 在上面的示例中，-2 和 1 是一个连续数组，-3 和 -1 是一个连续数组，2 和 1 是一个连续数组。 如果我们认为元素 {-2, 1, -1, 2} 是非连续数组，因为我们在这里有一个中断。

这里，我们需要一个具有最大和的连续子数组。 解决此问题的方法是，首先，我们找到所有可能的子数组，然后找到具有最大和值的子数组。 这会导致二次时间或三次时间。

考虑下面给出的数组

B: {-5, 4, 6, -3, 4, 1}

有多种技术可以解决此问题。 首先，我们看看蛮力来解决这个问题。 在蛮力的情况下，首先，我们必须找到所有的子数组，然后我们查看具有最大和的子数组。

以下算法用于实现蛮力

上面的算法的时间复杂度为 O(n²)。 时间复杂度很高，因此我们需要优化问题。 为了优化问题，我们使用 Kaden 算法。

什么是 Kaden 算法？

Kaden 算法是一种迭代动态编程算法，用于查找最大连续子数组。 使用 Kaden 算法，我们应该只考虑数组的正元素，并只跟踪最大连续和子数组。

Kaden 算法

让我们运行一下代码。

如果数组是 A: {5, -4, -2, 6, -1}

当 i=0;

A[0] = 5

current_sum = current_sum + A[0]

= 0+5 = 5

由于 current_sum > maximum_sum，即 5 > 0，所以

maximum_sum = 5

当 i = 1;

A[1] = -4

current_sum = current_sum + A[1]

= 5 - 4 = 1

由于 current_sum < maximum_sum，因此 maximum_sum!= current_sum

当 i = 2;

A[2] = -2

current_sum = current_sum + A[2]

= 1 - 2 = -1

由于 current_sum < maximum_sum，因此 maximum_sum 不等于 current_sum。 current_sum 的值为负，因此 current_sum 等于 0。

当 i = 3;

A[3] = 6

current_sum = current_sum + A[3]

= 0 + 6 = 6

在这种情况下，current_sum 大于 maximum_sum，即 (6>5)，因此 maximum_sum 等于 current_sum，即 6。

当 i = 4;

A[4] = -1

current_sum = current_sum + A[4]

= 6 - 1 = 5

由于 current_sum<maximum_sum，因此 maximum_sum 不等于 current_sum。

因此，连续数组的 maximum_sum 为 6。

C 语言实现

// 用于实现最大和连续数组的程序

输出