Доброго времени суток.

Задали тут задачку на собеседовании. Я сам в программировании пока новичок.

Есть произвольно заполненный массив int array[]. могут быть, как положительные, так и отрицательные значения.
Смысл такой, что значение суммы например элемента 3 будет равен сумме всех предыдущих элементов, ещё к тому же все это считается по модулю, т.е. sum(3) = | array[3] + array[2] + array[1] + array[0] |
Как найти минимальную сумму?

Я предложил, перебрать все элементы в двух циклах и сохранять значение в переменную, ну т.е. по сути на подобии пузырька. Сказали, что работать будет, но не оптимально.

Подскажите, плз, что будет являться оптимальным решением. Если нетрудно, то с кодом.