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。

我怎样才能让它也适用于负数？

谢谢！

原文由 David Gomes 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

根据 Wikipedia ，Kadane 的算法至少需要一个正数，因此您的所有负数数组都是无效输入。

原文由 Mark Elliot 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

当所有元素都是负数时，最大子数组是空子数组，其和为 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);

原文由 Marcelo Menegali 发布，翻译遵循 CC BY-SA 3.0 许可协议