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

Question

Objective: Evaluating the algorithm for finding the largest sum in a continuous subarray below.

Note: written in C++

As I was looking into the problem that Kadane successfully solved using dynamic programming, I thought I would find my own way of solving it. I did so by using a series of recursive calls depending on whether the sum can be larger by shorting the ends of the array. See below.

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
   }
}

I understand that Kadane's algorithm takes O(n) time. I am having trouble calculating the Big O of my algorithm. Would it also be O(n)? Since it calculates the sum using O(n) and all calls after that use the same time. Does my algorithm provide any advantage over Kadane's? In what ways is Kadane's algorithm better?

You are always recalculating the sum. O(N^2) complexity in the worst case — Damien
Moreover, I am not convinced your algorithm provides the good result. Test it with (1, -2, 5, -2, 1) — Damien

trincot trincot · Accepted Answer · 2020-02-01T09:09:58

First of all, the expression sum-array[0]>sum is equivalent to array[0]<0. A similar observation applies to those other conditions you have in your code.

Your algorithm is incorrect. The comment you have here is not true:

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

When you get at that point you know that the outer two values are both positive, but there might be a negative-sum subarray somewhere else in the array, which -- when removed -- would give two remaining subarrays, of which one (or both) could have a sum that is greater than the total sum.

For instance, the following input would be such a case:

[1, -4, 1]

Your algorithm will conclude that the maximum sum is achieved by taking the complete array (sum is -2), yet the subarray [1] represents a greater sum.

Other counter examples:

[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?

1 Answers