Список разборов

Можно решить через простую рекурсию.
В переменной s будем хранить сумму всех цифр.
Затем вызываем рекурсию rec(1,a[1],s-a[1]);

int rec(int x,int s1,int s2) // в переменной s1 хранится сумма всех цифр слева x,а s2 справа ...

Эту задачу можно решить при помощи RSQ (решение "втупую" может и не пройти). Просто строим бинарное дерево за O(N), затем пускаем цикл с 1 до N, и находим максимальную сумму (за O(NlogN)) на отрезке (1-i,i-N). В итоге эффективность нашего алгоритма...