Search code examples
arraysalgorithmminimumkadanes-algorithm

Minimum sum with subarray length > 0

Given an array of numbers, find the minimum sum and the subarray cannot be of length 0.

I know I can use kadane's algorithm but the question requires that the length of subarray should not be 0. Hence, my implementation can't handle the cases where all the elements of the array are positive.

For example, given the following array: 2, 5, 3, 8, 4, minimum sum is 2.

It also has to work on normal arrays like: -5, -4, 5, -1, 2, minimum sum is -9 (sum of first two elements)

How do I achieve this?

Here is my implementation:

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

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

  • Just use kadena's algorithm, and if the answer is an empty subarray, instead find the least element in your array.