Kadane 算法

Kadane 算法是从所有子数组中找到和最大的子数组的最佳算法。

arr[]={-5, 4,  6, -3 , 4, -1}

在这个数组中，子数组 {4, 6, -3 , 4 } 的和最大。

解决这个问题的最简单方法是计算所有子数组的和，然后输出和最大的子数组。但这种方法需要进行两次遍历，因此时间复杂度为n² 。 

使用 Kadane 算法可以大幅降低时间复杂度。

方法

只要子数组中的元素为正数，我们就可以把它加到总和中。 

因此，如果任何子数组的累积和为负数，就舍弃这一部分。 

从头开始累加元素，并记录累积和的最大值。如果总和变成负数，就舍弃这一部分，并从下一个索引重新开始。

1. 创建两个变量 maxSum 和 cumSum，并将它们都设为 0。

2. 运行一个从 0 到 n 的循环。

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
  
}

3. 按如下方式计算子数组的累积和：

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
}

4. 如果 cumSum 大于 maxSum，就将它存入 maxSum。

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
   
   if(cumSum>maxSum){
      maxSum=cumSum;
   }
}

5. 如前所述，如果累积和变成负数，就舍弃这一部分。因为它能产生的最大和已经存储在变量 maxSum 中。因此，如果 cumSum 变成负数，就将它重新设为 0，并从下一个索引重新开始，如下所示：

int maxSum=0, cumSum=0;
for(int i=0;i<n;i++){
   cumSum=cumSum+arr[i];
   
   if(cumSum>maxSum){
      maxSum=cumSum;
   }
   
   if(cumSum<0){
      cumSum=0;
   }
}

6. 遍历整个数组后，最大和会存储在变量 maxSum 中。

请记住，如果子数组的最大和为负数，就必须相应地修改函数。你可以自己试试看。

时间复杂度分析

由于我们只遍历数组一次，因此时间复杂度为O(n)。这比之前的方法有了很大的改进。

想进一步了解 Kadane 算法，请参阅：

Kadane 算法