介绍：
Kadane国彩网是解决最大子数组问题的有效方法。
说明：
因此，在我们了解Kadane国彩网之前，首先我们要看一下这是最大子数组问题吗？
您将得到一个数组，您需要找到其和为最大和的连续子数组。
例如，考虑以下数组：
[-1，0，2，3，-2]
在上面的数组中，您需要找到一个具有最大和的子数组。
通过蛮力我们可以看到元素[2，3]的和为5。这是最大和。
如果用蛮力解决，将花费O（n）的时间。可以在Kadane的帮助下有效地解决’s algorithm.
前往kadane之前’的国彩网，我们将看到如何通过蛮力方法求解：
在任何索引处，我们检查该索引处的最大子数组是多少：
因此，对于我们的示例
[-1，0，2，3，-2]
For the first index it is -1
For the second index it could be max ( [-1 + 0], [0] ) Hence max = 0;
For the third index it could be max ( [-1 + 0 + 2], [0 + 2] [2] ) Hence max = 2;
For the forth index it could be max ( [-1 + 0 + 2 + 3], [0 + 2 + 3] [ 2 + 3] [3] ) Hence max = 5;
因此，暴力破解中最差的情况是O（n ^ 2）。
通过使用kadane’的国彩网，我们可以将其减少到O（n）时间。
Kadane国彩网的工作步骤如下：
1.局部最大子数组是当前索引处的元素
要么
2.当前元素与先前的局部最大子数组组合。
我们将继续为数组中的所有元素计算上述值。之后，我们将在local_max_sub_array列表中选择最大子数组。
那么如何以编程方式进行呢？
Step 1: take 2 variables: local_max_sub_array = a[0] global_max_sub_array = a[0] Step 2: Start a loop from index 1 to end of the array and perform below operation: local_max_sub_array = max(arr[i], local_max_sub_array + arr[i]) global_max_sub_array = max (local_max_sub_array, global_max_sub_array) Step 3:Return the global_max_sub_array.
使用示例了解Kadane国彩网：
给定数组：[-1，0，2，3，-2]
Initally local_max_sub_array = a[0] = -1 global_max_sub_array = a[0] = -1
Pass 1: local_max_sub_array = max[arr[1], (-1 + arr[1])] = max [0, -1] = 0 global_max_sub_array = max(0, -1) = 0
Pass 2: local_max_sub_array = max[arr[2], (0 + arr[2])] = max [2, 2] = 2 global_max_sub_array = max(0, 2) = 2
Pass 3: local_max_sub_array = max[arr[3], (2 + arr[3])] = max [0, 5] = 5 global_max_sub_array = max(3, 5) = 5
Pass 4: local_max_sub_array = max[arr[4], (5 + arr[4])] = max [-2, (5 - 2)] = 3 global_max_sub_array = max(3, 5) = 5 Hence the sum of maximum sub array is 5.
用C ++实现
#include<stdio.h>
int kadane_algorithm(int a[], int size)
{
int i;
int max_sum_so_far=0;
int max_ending_here = 0;
for(i=0;i<size;i++)
{
max_ending_here = max_ending_here + a[i];
if(max_ending_here < 0)
{
max_ending_here =0;
}
if(max_sum_so_far < max_ending_here)
{
max_sum_so_far = max_ending_here;
}
}
return max_sum_so_far;
}
int main(){
int i,size;
printf("Enter the size of the array ");
scanf("%d",&size);
int a[size];
printf("\n Enter the elements of the array");
for(i=0; i<size; i++)
{
scanf("%d",&a[i]);
}
int max_sum = kadane_algorithm(a,size);
printf("\n The Maximum Sum of the Sub Array is : %d",max_sum);
return 0;
}
输出量
Enter the size of the array 5 Enter the elements of the array-1 0 2 3 -2 The Maximum Sum of the Sub Array is : 5
在所有情况下，Kadane的时间复杂度均为O（n）时间[线性时间]。
有一种滑动窗口方法可以解决此问题。在下一章中，我们将看到该国彩网的一个变体。
