Kadane算法负数

Question

int array[] = {-1, 4, -2, 5, -5, 2, -20, 6};

如果我有那个数组,我的Kadane算法实现找到最大的子数组工作:

  int max_so_far = INT_MIN;
  int max_ending_here = 0;
  for (int i = 0; i < size; i++) {
    max_ending_here = max(max_ending_here + array[i], 0);
    max_so_far = max(max_ending_here, max_so_far);
  }

  printf("%d\n", max_so_far);

但是,如果我有一个所有负数的数组:

int array[]= {-10, -10, -10};

它不起作用,它应该返回-10,但我得到0.

我怎样才能让它对负数起作用？

谢谢!

Answer 1

当所有元素都为负数时,最大子数组是空子数组,其总和为0.

但是,如果要在此情况下更改算法以存储最大元素,则可以执行以下操作:

int max_so_far      = INT_MIN;
int max_ending_here = 0;
int max_element     = INT_MIN;

for (int i = 0; i < size; i++)
{
    max_ending_here = max(max_ending_here + array[i], 0);
    max_so_far      = max(max_ending_here, max_so_far);
    max_element     = max(max_element, array[i]);
}

if (max_so_far == 0)
  max_so_far = max_element;

printf("%d\n", max_so_far);

Answer 2

根据维基百科,Kadane的算法需要至少一个正数,所以你的所有负数组都是无效输入.

Answer 3

int max_so_far = INT_MIN;
int max_ending_here = array[0];
for (int i = 1; i < size; i++) {
    max_ending_here = max(max_ending_here + array[i], array[i]);
    max_so_far = max(max_ending_here, max_so_far);
 }
 printf("%d\n", max_so_far);

它可能有效