Есть ли у этого рекурсивного алгоритма поиска наибольшей суммы в непрерывном подмассиве какие-либо преимущества?

Question

Цель: оценка алгоритма для нахождения наибольшей суммы в непрерывном подмассиве ниже.

Примечание: написано на C ++

Поскольку я изучал проблему, которую Кадане успешно решил с помощью Dynami c программирование, я думал, что найду свой собственный способ ее решения. Я сделал это с помощью серии рекурсивных вызовов в зависимости от того, может ли сумма быть больше, если закоротить концы массива. См. Ниже.

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

Я понимаю, что алгоритм Кадане занимает O (n) времени. У меня проблемы с вычислением Big O моего алгоритма. Это также будет O (n)? Поскольку он вычисляет сумму, используя O (n), а все вызовы после этого используют одно и то же время. Мой алгоритм дает какое-то преимущество перед алгоритмом Кадане? Чем алгоритм Кадане лучше?

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]