0

目标：评估在下面的连续子数组中找到最大和的算法。

注意：用 C++ 编写

当我研究 Kadane 使用动态编程成功解决的问题时，我想我会找到自己的解决方法。我通过使用一系列递归调用来做到这一点，具体取决于通过缩短数组的末端是否可以使总和更大。见下文。

int corbins_largest_sum_continuous_subarray(int n, int* array){
   int sum = 0; // calculate the sum of the current array given
   for(int i=0; i<n; i++){sum += array[i];}

   if(sum-array[0]>sum && sum-array[n-1]>sum){
      return corbins_largest_sum_continuous_subarray(n-2, array+1);
   }else if(sum-array[0]<sum && sum-array[n-1]>sum){
      return corbins_largest_sum_continuous_subarray(n-1, array);
   }else if(sum-array[0]>sum && sum-array[n-1]<sum){
      return corbins_largest_sum_continuous_subarray(n-1, array+1);
   }else{ 
      return sum; // this is the largest subarray sum, can not increase any further
   }
}

我知道 Kadane 的算法需要 O(n) 时间。我在计算算法的大 O 时遇到问题。它也会是O（n）吗？因为它使用 O(n) 计算总和，之后的所有调用都使用相同的时间。我的算法比 Kadane 的算法有什么优势吗？Kadane 的算法在哪些方面更好？

4

1 回答 1

1

首先，表达式sum-array[0]>sum等价于array[0]<0。类似的观察适用于代码中的其他条件。

你的算法不正确。您在这里的评论不正确：

}else{
    return sum // this is the largest subarray sum, can not increase any further
}

当你到达那个点时，你知道外面的两个值都是正数，但是在数组的其他地方可能有一个负和子数组，当被删除时，它会给出两个剩余的子数组，其中一个（或两者）的总和可能大于总和。

例如，以下输入就是这种情况：

[1, -4, 1]

您的算法将得出结论，通过获取完整数组（总和为 -2）来实现最大总和，但子数组 [1] 表示更大的总和。

其他反例：

[1, 2, -2, 1]
[1, -3, -3, 1, 1]
于 2020-02-01T09:09:58.920 回答