일단 해당 문제는 DP인것부터 빡친다.
DP란 필자가 제일 싫어하는 유형이기도 하지만,
없으면 시간복잡도가 안드로메다로 날라가버리는 만큼,
프밍에 있어서 매우 중요한 요소라고 할 수 있다.
특히나, 모든 경우의 수를 빠른시간안에 구한다는, 장점이 존재하므로
정말로 많은 프로그래머들이 애용하는 기법이기도 한데..
점화식 찾아내는게 너무 싫어서 코딩테스트에서는 절대로 만나고 싶지 않은 친구이다.
문제 자체에 함정카드가 너무 많이 숨겨져있어, 일단은 한 숨 부터 쉬고 들어가겠다.
또한, 문제는 덧셈과 뺄셈밖에 안하는데, 왜 사칙연산임? 이칙연산 아님?

각설하고, 이 문제가 얼마나 빡치는 문제인지 알아보도록 하자.
문제의 유형을 모른다고 하고, 문제만 놓고 보면, DFS로 완전탐색을 해야할 것 같은 느낌이 든다.
그렇지만, 레벨을 보자면, 4레벨에 해당하므로, 시간이 안드로메다로 떠나버리는 DFS를 쓸 용기는 사라질 것이다.
보통 효율성을 보는 문제는 DFS나 BFS는 거른다고 생각하면 편할 것이다.(항상 그런건 아님 -_-;;)

그럼 완전탐색을 해야할 것 같긴 한데 뭘로 할까 고민하는 여러분들을 위해,
DP라는 것이 있습니다. 이 친구는 완전탐색에 발생하는 중복적인 요소를 확실히 제거하여,
소요시간을 기하급수적으로 줄여주는 친구이다.

DP를 통해, 해당 숫자에서 나오는 모든 경우의 수를 계산하여 결과의 최댓값을 구해보도록 하자.
문제에서 알다시피 해당 문제는 순서는 바뀌지 않는 것을 쉽게 알 수 있다.
즉, 이 문제는 숫자를 계산하는 순서에만 상관이 있고, 숫자의 순서 자체는 절대 변해서는 안된다.
부호하고, 숫자는 항상 정위치에서 존재하는 상태에서 연산의 위치에 따른 경우의 수를 구해야 한다.

예시를 한 번 들어보자

10 - 5 + 7 + 9 - 20 - 30 + 10

위와 같은 예시가 존재한다고 하자. 우리는 어떻게 계산해야 전부다 연산하였을 경우의 최댓값을 산출할 수 있을까?
일단 한가지 확실한 것은 존재한다. 자기 자신만 연산했을 경우의 최댓값은 항상 자기 자신이 된다.
이유는 말안해도 알거다. 자기 자신은 할 수 있는 연산이 존재하지 않기 때문이다.
그럼 해당 사실로 부터 그 다음 단계로 나아가보자. 자기 자신과 오른쪽 하나 옆에 떨어친 친구와 연산을 수행하면,
그 최댓값은 얼마가 될까? 이것도 쉽게 연산이 가능하지 않은가? 자기 자신과 연산할 수 있는 친구는 하나 밖에 존재하지 않는다.
당연히 오른쪽 하나 떨어진 친구와 연산한 결과가 항상 최댓값임을 보장할 수 있을 것이다.
위의 경우로 예를 들면, 10의 오른쪽 하나 떨어진 친구 5와 연산을 수행하면 항상 5임을 보장하고, 그 값 이외에는
나올 수 있는 연산이 불가능하다. 이런 걸 하나씩 오른쪽으로 시프트하여 쭉 연산을 수행해본다.

[10-5, 5+7, 7+9, 9-20, 20-30, 30+10] => [5, 12, 16, -11, -10, 40]

위와 같은 결과가 산출된다. 해당결과는 자기자신 기준으로 오른쪽 하나 떨어진 친구와 계산을 수행한 결과이다.
여기서 중요한 점은 수식 중간에 -5와 같은 항이 존재하더라도, -와 5는 서로 확실히 구별되어야 한다.
우리는 각각의 숫자를 어떤 순서대로 계산하느냐에 따른 결과를 알고싶은 것이다. -는 단순히 연산기호일뿐이다.
이 부분을 절대로 착각해서는 안된다. 위의 수식을 참고하여, 결과가 왜 저렇게 나왔는지 확인하도록 하자.
중요한 것은 그 다음이다. 이게 이 문제의 핵심포인트이다.

1번째 부터, 3번째 까지 연산을 수행할 경우, 최댓값은 얼마일까? 우리는 아까 하나만 연산하면 자기 자신이 최댓값이고,
오른쪽 하나 떨어진 친구와 연산하면, 어떤 값이 출력이 되는지를 알고 있다.
연산했던 2가지의 결과를 적절히 조합하면, 1번에서 두 개나 떨어진 부분까지의 최댓값을 알 수 있지 않을까?
그렇다, 1~3을 전체 식에서 가져와보자. '10 - 5 + 7' 이다. 여기서 10과 (5 + 7)의 차를 계산하는 방법도 있고,
(10 - 5)와 7의 합을 계산하는 방법또한 있다는 사실을 알 수 있다.
그렇다. i부터 j까지의 최댓값을 산출하고 싶으면, 시작부분과 끝부분 두 영역으로 나누고,
시작부분을 하나씩 올리고, 끝부분을 하나씩 줄이면서, 최댓값 연산을 수행하면 된다.

위의 계산식에서 처음부터 끝까지의 값의 연산결과를 구하고 싶다면,

step1 = 10 - ( 5 + 7 + 9 - 20 - 30 + 10)
step2 = (10 - 5) + (7 + 9 - 20 - 30 + 10)
step3 = (10 - 5 + 7) + (9 - 20 - 30 + 10)
step4 = (10 - 5 + 7 + 9) - (20 - 30 + 10)
step5 = (10 - 5 + 7 + 9 - 20) - (30 + 10)
step6 = (10 - 5 + 7 + 9 - 20 - 30) + 10

위와 같은 연산의 순서대로 진행된다. 물론 우리는 자기자신만 연산했을 경우는 알고있지만,
괄호안에 든 3개 이상의 연산을 수행했을 경우나, 이런 것들은 차근 차근 구해야한다.
근데 모르는 사람의 위의 수식만 보면, 착각에 드는 것이 존재한다.
바로, 괄호를 그냥 계산한다는 생각이다. 괄호 안에든 수식은 해당 수식을 계산한 경우의 최댓값을 의미한다.
즉, 위의 예시는 최종적으로 정답을 산출하기 위해서 필요한 것이다. 괄호가 숫자를 몇개를 품고있는지 계산해보면,
자기자신만 연산한 경우, 하나 떨어진 친구와 연산한 경우, 두 개 떨어진 친구와 연산한 경우.... n-1떨어진 친구와 연산한 경우.
결국 낮은 순서부터 위와 같은 경우의 수를 DP연산으로 저장해야함을 알 수 있다.
낮은 단계에서 계산 해둔 연산을 높은 단계에서 재활용함으로써 중복연산을 획기적으로 단축하는 것이 가능하다.

그런데 여기까지 알아서 계산했으면 참으로 좋겠지만, 이 문제는 아주 돌아버리는 함정을 내포하고 있다.
빠로 뺄셈 연산의 최댓값이라는 점이다.
덧셈 연산의 최댓값은, 아마 잘 알 것이다. 그냥 높은 값 2개 연산하면 아주 나이스하게 끝난다.
그런데 뺄셈은 높은 값 2개 빼면, 그게 최댓값이라고 할 수 있겠는가? 절대 아니다.
여기서 상식적으로 생각해보자. 뺼셈은 어떨 때 가장 큰 값을 남길 수 있는가?
당연히 제일 큰 값에서 제일 작은 값을 뺐을 경우가 된다.

그렇게 된다면, 뺼셈 연산때문에, 가장 큰 값의 경우를 저장하는 DP뿐만 아니라,
가장 작은 값의 경우를 저장하는 DP 또한 추가적으로 생성이 필요하다는 의미가 된다.
이해가 되는가? 뺄셈연산으로 인해 현재 구간의 최솟값이 필요하고, 현재 구간의 최솟값을 구하려면,
현재 구간의 최솟값을 저장하는 DP또한 필요하게 된다는 것이다.

그럼 이제 DP를 정의해보자.
여기서 말하는 DP의 정의는 다음과 같다.

MAX_DP[i][j] = i번째 부터 j번째까지 구간의 연산의 최댓값
MIN_DP[i][j] = i번째 부터 j번째까지 구간의 연산의 최솟값
단, DP는 이차원 배열, 각 차원의 길이는 숫자의 개수만큼임.

위와 같다. 당연히 MAX_DP의 초깃값은, 음의 무한대가 되야 올바른 max값을 도출해낼것이다.
또한 MIN_DP의 초깃값은, 양의 무한대가 되야 올바른 min값을 도출해낼것이다.

코드의 구조를 살펴보자.
필자는 파이썬을 좋아하므로, 파이썬으로 대충 알아보겠다.

INF = 987654321
n = 숫자 갯수임.
MIN_DP = [[INF for _ in range(n)] for _ in range(n)]
MAX_DP = [[-INF for _ in range(n)] for _ in range(n)]

for step in range(len(DP)): #i와 j의 간격.

    for i in range(len(DP)-step): #i부터 j까지의 연산을 수행함.

        j = i + step

        if step == 0:
            DP[i][i] = 해당되는 숫자
        else:
            for k in range(i, j): #i 부터 j까지 돌면서, 괄호를 하나는 늘리고, 하나는 줄여서 각각의 범위 연산을 수행함.
                if k번째의 연산자 == '+': #k번째에 해당되는 연산이 + 일 경우:
                    MAX_DP[i][j] = max(MAX_DP[i][j], MAX_DP[i][k] + MAX_DP[k+1][j]) # + 일 경우 최댓값은 최댓값 + 최댓값임.
                    MIN_DP[i][j] = min(MIN_DP[i][j], MIN_DP[i][k] + MIN_DP[k+1][j]) # + 일 경우 최솟값은 최솟값 + 최솟값임.
               else: #k번째에 해당되는 연산이 - 일 경우.
                    MAX_DP[i][j] = max(MAX_DP[i][j], MAX_DP[i][k] - MIN_DP[k+1][j]) # - 일 경우 최댓값은 최댓값 - 최솟값임.
                    MIN_DP[i][j] = min(MIN_DP[i][j], MIN_DP[i][k] - MAX_DP[k+1][j])# - 일 경우 최솟값은 최솟값 - 최댓값임.

return MAX_DP[0][n-1]

이 코드에서 점화식을 대충 볼 수 있다.

DP[i][j] = max(MAX_DP[i][j], MAX_DP[i][k] + MAX_DP[k+1][j])

기본형은 위와 같지만, -연산자가 존재함에 따라 위의 코드처럼 3가지의 형태로 변형이되어 파생되는 것을 알 수 있다.
step이라는 것을 통해 범위를 낮은 단계부터 순차적으로 올리면서, 손쉽게 연산할 수 있게 도와준다.
당연히 DP를 최초로 선언할 경우, 양이나 음의 무한대 값만 들어있으므로, 실질적인 값은 들어있지 않게된다.
그렇지만, step이 0일 경우에는 자기자신만 연산하는 결과에 해당하므로, DP에 자기자신을 대입함으로써 계산을 시작할 수 있게 된다.
위에서 연산자의 구분에 따라, MAX DP와 MIN DP를 구하는데 많은 혼란이 야기될 것으로 생각한다.
위의 코드를 보면 알겠지만, 답은 MAX_DP의 0부터 n-1번째 까지의 계산값임을 알 수 있다.
그게 문제에서 요구하는 것이니 당연한 것이다.

그렇지만, 위에서도 말했지만, 현재까지의 설명을 보고서도 너무 대충읽은 탓인지, MIN_DP왜 필요한 거지?
라고 생각할 수도 있을 것이다. 물론 아니라면, 돌아가서 다시 문제를 풀어도 좋을 것이다. 답을 거의 알려줬으니 ^_;;

위의 파이썬 코드를 대충봤을 때, MAX_DP만 계산해도 굳이 답에 영향을 주지 않을 것 처럼 보일 것이다.
왜냐하면, MIN_DP가 필요한 이유가 수식 하나때문에 필요한 부분이기 때문이다.

MAX_DP를 계산하려면, 당연히 가장 큰 값을 계산해야 하니 MAX_DP에 있는 값을 불러와서 계산하면 될 것이다.
하지만, 그건 덧셈에 한해서 해당되는 말이다.
우리는, - 라는 연산자가 어디 도망가서 +로 변한다는 생각을 하지 말아야한다.
3 - 5 라는 수식이 있을 경우, 우리는 이걸 3하고 5가 있고 그걸 연결해주는 부호가 - 구나 라고 생각해야한다는 것이다.
이걸 3하고 -5를 +로 더한다고 생각하면, 이 문제를 이해하는데 있어 많은 혼란을 야기 할 것이다.

그러면, 다음과 같은 의문이 든다. MAX_DP를 갱신하려는데, 현재 계산하는 부호가 - 일 경우는 어떻게 해야하지?
그런데 여기서 생각을 안하다보면, 그냥 빼버리면 되는거 아님? 이렇게 생각할 수 있다.
하지만, 지금 푸는 문제는 모든 경우의 수를 찾아내는 문제이다. 그 중에서도 MAX_DP[i][j]는 i ~ j 구간의 연산 결과의 최댓값이다.
그런데 그 두값을 그냥 빼버린다고? MAX_DP가 있다는 말은, 원래 그 구간에서의 연산 결과가 낮은 구간도 분명 존재할 것이다.
그렇기에, MIN_DP를 만들어 MAX_DP에서 MIN_DP를 빼버리는 연산을 수행하게 된다.
우리는 단지 MAX_DP가 - 부호를 만났을 경우를 대처하기 위해서, MIN_DP라는 것을 만들 필요가 존재했다.
그래서 MIN_DP도 연산할 때마다, 계속 연산해줘야 한다.

말이 조잡하지만, 도움이 됬으면 좋겠습니다. 20000