c++ - 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);