Дан массив \(a\), состоящий из \(n\) целых чисел. Ваша задача — разбить \(a\) на непустые подотрезки (всего существует \(2^{n-1}\) таких разбиений).
Пусть \(s=a_l+a_{l+1}+\ldots+a_r\). Значение подмассива \(a_l, a_{l+1}, \ldots, a_r\) равно:
- \((r-l+1)\), если \(s>0\),
- \(0\), если \(s=0\),
- \(-(r-l+1)\), если \(s<0\).
Какую максимальную сумму значений подотрезков можно получить при оптимальном разбиении?
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную сумму значений подотрезков, которую можно получить при оптимальном разбиении.
Примечание
Пример \(1\): одно из оптимальных разбиений выглядит так: \([1, 2]\), \([-3]\). \(1+2>0\), поэтому величина \([1, 2]\) равна \(2\). \(-3<0\), поэтому величина \([-3]\) равна \(-1\). \(2+(-1)=1\).
Пример \(2\): возможное оптимальное разбиение выглядит так: \([0, -2, 3]\), \([-4]\), сумма величин подотрезков равна \(3+(-1)=2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 2 -3
4
0 -2 3 -4
5
-1 -2 3 -1 -1
6
-1 2 -3 4 -5 6
7
1 -1 -1 1 -1 -1 1
|
1
2
1
6
-1
|