这种寻找连续子数组中最大和的递归算法有什么优势吗？

Question

Objective: 评估求下面连续子数组中最大和的算法

注意：用 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 的算法在哪些方面更好？

Answer 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]

这种寻找连续子数组中最大和的递归算法有什么优势吗？

Does this recursive algorithm for finding the largest sum in a continuous sub array have any advantages?

c++

algorithm

big-o

time-complexity

kadanes-algorithm