arrays - 子数组长度 > 0 的最小和

Question

给定一个数字数组，找到最小和并且子数组的长度不能为 0。

我知道我可以使用 kadane 的算法，但问题要求子数组的长度不应为 0。因此，我的实现无法处理数组的所有元素都为正数的情况。

例如，给定以下数组:2, 5, 3, 8, 4，最小和为2。

它还必须在普通数组上工作，例如:-5, -4, 5, -1, 2，最小和为-9(前两个元素之和)

我如何实现这一目标？

这是我的实现:

while (N--) {
    scanf("%i", &num);

    localmx += num;
    if (localmx > 0) localmx = 0;
    if (localmx < mx) mx = localmx;
}

Answer 1

只需使用 kadena 算法，如果答案是一个空子数组，则改为查找数组中最少的元素。