문제의 의도로 보이는 min, max 2차원 DP를 이용한 풀이O(n**2)는 나와 있으니,
다른 풀이도 적어 봅니다
　
이 문제에서는 연산해야 할 항이 최대 101개 이지만,
천만개 가까이 주어져도 통과 가능한 풀이 되겠습니다.
　

step1) 뺄셈 탐구

덧셈과 곱셈은 연속적으로 주어져 있을 때 계산순서에 영향을 받지 않습니다.

A+B+C = (A+B)+C = A+(B+C)

따라서 연속적으로 항이 주어지더라도 굳이 계산 순서를 지정해 줄 필요가 없으며
다시말해, 괄호를 써서 식을 지저분하게 할 이유가 없습니다.
이를 '결합법칙' 이 성립한다고 합니다. (고1 수학시간 때..)
(--> 덧셈과 곱셈만이 결합법칙이 성립합니다)
　
한편 실수집합R같은 수 집합에 연산을 부여할 때,
뺄셈과 나눗셈은 따로 직접 정의하지 않습니다.
덧셈과 곱셈만 정의하면 뻴셈과 나눗셈은 각각 덧셈과 곱셈에 기대어 정의 할 수 있기 때문인데요
(--> (R,+,×): 사칙연산 충분!)
　

뺄　셈 A - B = A + (B의 덧셈 역원)
나눗셈 A ÷ B = A × (B의 곱셈 역원)

위와 같이 뺄셈 대신 덧셈을, 나눗셈 대신 곱셈으로 바꾸어서 계산하도록 정의합니다.
여기서 B의 덧셈 역원이란 B만큼 더했을 때 복구시켜주는 수라고 보면 됩니다.
예를들어) 3만큼 더했다면, 복구를 위해서는 그 반대 부호인 (-3)만큼 더하면 되므로
빼기 3은 더하기 (-3)이 됩니다.
　
최종적으로 두 연산의 정의는 아래처럼 됩니다.

뺄　셈: A - B = A + (-B)  --> 뒷 항을 부호 바꿔 더한다
나눗셈: A ÷ B = A * (1/B) --> 뒷 항을 역수로 바꿔 곱한다

　
하고 싶었던 말
--> 뺄셈 연산의 본질: '뒷 항 부호 바꾸어 더하기'
　

step2) 청사진

앞서 말씀드렸듯이 뺄셈과 나눗셈은 결합법칙이 성립하지 않습니다.
따라서 문제에서 뺄셈 연산은 딱 그 횟수만큼만 반드시 괄호를 이용해서 순서를 지정해 줘야 합니다.
　
아래 간단한 예시를 봅시다.

0 - 3 + 2 + 1

괄호가 1번만 지정되면 됩니다. 괄호를 1번만 그리는데,
뺄셈 연산의 뒷 항이 어디까지 먼저 계산되었는지 모든 경우를 살펴봐야 합니다.

경우1)　0 - (3) + 2  + 1  = 0 + (-3) +   2  +   1
경우2)　0 - (3  + 2) + 1  = 0 + (-3) + (-2) +   1
경우3)　0 - (3  + 2  + 1) = 0 + (-3) + (-2) + (-1)

각각의 경우 모두 뺄셈을 덧셈으로 바꿈으로써 이제 모든 연산이 덧셈이므로
연산 순서가 상관없는 식이 되었고, 대신 몇몇 항이 음수가 되었습니다.
괄호가 어디까지 포함되느냐에 따라 연속적으로 이후 부호를 전부 바꿔야 합니다.
　
문제에서 항마다 주어지는 수는 모두 양수이므로
뺄셈 연산이 1개 뿐일 때는
--> 괄호가 멀리 쳐진만큼 전체 값은 작아지므로
--> 최댓값은 맨 앞 값만 음수 전환할 때, 그리고 최솟값은 그 뒤로 전부 음수전환할 때가 됩니다.
　
여기서 한 가지 문제점이 있습니다.
우리는 다항식을 보면서 첫 뺄셈 연산 단 1번을 계산하고 싶었을 뿐인데,
이 한 번의 연산을 위해서 뒷 항의 괄호가 어디 까지 뻗친줄(먼저 계산됨) 모르므로??
모든 식을 끝까지 다 읽고 모든 경우를 싹 다 탐색해야 합니다 (ㅡ.ㅡ)
　
하지만 우리는 뺄셈에서 앞 항 값은 전혀 변화가 없고 않고
'뺄셈 기호 뒷 항들'의 부호만 직후부터 연속적으로 일정 갯수만큼 바뀔 수 있는 것을 알기 때문에,
--> 식을 뒤에서 부터 계산하는게 확정적이고, 고로 매우 효율적입니다!
　
또 한가지 생각해야 할 점이 있습니다.
--> 최댓값 뿐 아니라 최솟값도 구해야 한다!는 점입니다.
　
뒤에서부터 모든 연산을 계산해 왔을 때, 맨 마지막 연산이 덧셈이면
즉 A+B… 로 시작하는 다항식일 경우 B의 최댓값이 필요하지만,
A-B… 로 시작하는 다항식일 경우 B의 최솟값이 필요하기 때문입니다.
　

step3) 문제 적용

이제 구체적으로 들어가기 위해 간단한 다항식을 봅시다
맨 처음에 뺄셈 연산이 1회 나오고, 이후로는 덧셈만 나오는 경우입니다.

0 - 3 + 2 + 1

이 다항식의 최댓값은 맨앞의 3만 부호를 바꿔 더한 (-3)+2+1 = 0 이 될 것이고
최솟값은 전체를 몽땅 부호 바꾼 -(3+2+1) = -6 이 될 것입니다.
　
이제 앞에 다항식이 조금 더 추가됩니다. 뺼셈 연산이 2개가 되었습니다.

0 - 6 + 5 + 4 - 3 + 2 + 1

다항식 뒤에서부터 살펴봅시다.
우리는 뺄셈 연산기호 좌측으로는 아무런 변화가 없다는걸 알기때문에,
우측에서부터 가장 먼저 나오는 뺄셈 기호를 기준으로
오른쪽만 반복해서 계산하면 된다는 것을 알 고 있습니다.
　
뒤에서부터 첫번째 뺄셈 연산 기준으로, 뒷 항 3개를 부분다항식 tail이라 하고 수들만 가져옵시다.
tail = [3, 2, 1]
tail의 최댓값은 첫 항 3만 음수로 바꿔 전체를 더한 0이었고,
tail의 최솟값은 전체를 음수로 바꿔 더한 -6이었습니다.
--> max_tail, min_tail = (0, -6)
　
우리는 뺄셈 정의에 따라 맨뒤 뺄셈 연산을 덧셈으로 바꾸면서
--> 앞에 있는 4까지는 아무런 변화가 없었고
--> 그 뒤 모든 항들의 연산 결과가 최대=0 또는 최소=-6 임이 될 수 있음을 알았습니다.
　
정리하면 아래와 같습니다.

0 - 6 + 5 + 4 + tail 　 (tail: -6~0)

또 익숙한 형태의 다항식이 나왔습니다.
(유일한 다른 점은 tail이 음수가 될 수도 있다!는 것 뿐입니다.)
　
그럼 이제, 다음 뺄셈을 기준으로 부분다항식 sub := [6, 5, 4] 라고 하고
전체 다항식의 최댓값, 최솟값을 구해봅시다.

  0 + sub       + tail 
= 0 - 6 + 5 + 4 + tail 　 (tail: -6~0)
당연히 sub의 최댓값과 tail의 최댓값만 구해 더하면 되는데..
sub 중에서 딱 6만 음수로 바꿔서
0 + (-6) + 5 + 4 + max_tail 이 최댓값이 되겠지!

라고 생각한다면 틀렸습니다...
　
이 때는 왜 다르냐면, 앞서 말했듯이 tail이 (절댓값이 상당히 큰) 음수가 될 수 있기 때문입니다.
sub[0] 뿐만 아니라 sub[1:] 인 모든 양수들 [5, 4]까지 전부 음수로 바꿔서라도
tail까지 전체를 괄호를 묶음으로써 tail의 부호를 바꾸는 경우가 전체값이 더 클 수 있습니다.

0 - 6 + 5 + 4 + (-100) 의 경우

0 + (-6) +   5  +   4  +   (-100) 보다
0 + (-6) + (-5) + (-4) + (-(-100)) 가 큽니다.

　
이제는 맨 뒤 tail 항이 '절댓값이 상당히 큰 음수'가 될 수 있다는걸 알았기 때문에,
앞에 있는 부분다항식 sub과 tail을 합쳐 계산할 때, sub의 음수 전환할 괄호를 어디까지 할지
아래 3가지 경우를 생각해야 합니다.(3가지 경우만 생각하면 됩니다)

      0 - 6  + 5  + 4  + tail 의 경우

후보1) 0 -(6) + 5  + 4  + tail  <-- sub 최대. max_sub + tail
      0 -(6  + 5) + 4  + tail  <-- 크지도 작지도 않아서 나가리..
후보2) 0 -(6  + 5  + 4) + tail  <-- sub 최소. min_sub + tail
후보3) 0 -(6  + 5  + 4  + tail) <-- tail 부호 바꿔주는 경우. min_sub - tail

(sub[1:] 은 모두 양수항들 뿐이기 때문에 위의 sub 예시에서 처럼
어중간한 5까지 하는 괄호는 양 극값을 찾는 시점에서 의미가 없습니다.)
　

최종 매커니즘 정리

이제 전체 다항식을 뺄셈 연산 기준으로 분할한 부분다항식들에 대해,
우측부터 tail의 최댓값, 최솟값을 반복적으로 갱신해 나갈 매커니즘을 정리해 봅시다!
　

  0 + sub       + tail 
= 0 - 6 + 5 + 4 + tail 　 (tail: -6~0)

두 부분다항식 sub과 tail을 합쳤을 때, 그 sub + tail 의 최댓값은 아래 둘 중 하나입니다.
경우1) max_sub + max_tail --> sub의 첫항만 음수 & tail의 최댓값
　= -sub[0] + sum(sub[1:]) + max_tail
경우2) min_sub - min_tail --> sub 전체를 음수로 바꿔 더해가면서까지 tail의 부호 바꿔 더하기
　= -sum(sub[:]) - min_tail
--> sub 전체를 괄호 씌워 음수로 바꿔야 하므로 sub은 min_sub이 되고,
--> tail 값을 부호 바꿔 더해야 하므로 tail 값은 최댓값이 아니라 최솟값을 가져와야 합니다.
　
마찬가지 방식으로 sub + tail 의 최솟값은 아래 둘 중 하나입니다.
경우1) min_sub + min_tail --> sub 전체를 음수 & tail의 최솟값
　= -sum(sub[:]) + min_tail
경우2) min_sub - max_tail --> sub 전체는 물론 tail 까지 괄호에 넣어서 부호 바꿔 더하기
　= -sum(sub[:]) - max_tail
--> sub 전체를 괄호 씌워 음수로 바꿔야 하므로 sub은 min_sub이 되고,
--> tail 값을 부호 바꿔 더해야 하므로 tail 값은 최솟값이 아니라 최댓값을 가져와야 합니다.
　
이제 모든 매커니즘이 정해졌습니다.
뺄셈 연산 좌측은 영향을 안 받으니, 우측에서부터 뺄셈 연산 기준으로 부분 다항식을 뽑아내서
반복적으로 tail의 최대/최솟값을 계산해 주면됩니다.