Минимальная сумма при длине подмассива ›0

Учитывая массив чисел, найдите минимальную сумму, и длина подмассива не может быть равна 0.

Я знаю, что могу использовать алгоритм Кадане, но вопрос требует, чтобы длина подмассива не была равна 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;
}

person Mohideen Imran Khan    schedule 05.07.2014    source источник


Ответы (1)


Просто используйте алгоритм Кадены, и если ответ - пустой подмассив, вместо этого найдите наименьший элемент в вашем массиве.

person pdw    schedule 05.07.2014