Поскольку тут прозвучали идеи относительно решения задачи C, предложу-ка и я свое решение (линейное) :)
 Идея в следующем:
1. Если искомые префикс и суффикс пересекаются, то общая их часть остается с искомым знаком, и следовательно этот случай эквивалентен случаю когда взяты те же суффикс и префикс, но без общей части, например:
(s1 [s2 )s3 ] эквивалентно  (s1)s2[s3] (s1,s2,s3 - некоторые подпоследовательности).
2. Пусть сумма последовательности элементов A1 .. An равна S. Тогда при инвертации знаков получаем -A1, -A2 .. -An, а сумма соответственно изменяется на -S, то есть сумма чисел на отрезке при инвертации просто изменит свой знак.
3.Исходную задачу можно рассмотреть в таком ракурсе: нужно выбрать из последовательности непрерывную подпоследовательность (ту, что останется между префиксом и суффиксом), а вне ее инвертировать все числа. Тогда если сумма чисел всей последовательности равна S, а сумма выбранной подпоследовательности S1, то итоговая сумма даст -(S-S1) + S1 = 2*S1 - S  -  это и есть та самая величина, которую нужно максимизировать. S- постоянная, => нужно максимизировать S1, т.е. найти в заданной последовательности непрерывную подпоследовательность с максимальной суммой, а это делается линейно:
mx = 0;