문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/1843

---

문제 파악

배열 arr가 문자열 토큰으로 주어진다.

• 숫자: "5", "3" …
• 연산자: "+", "-"

이 토큰 순서를 유지한 채로 괄호를 적절히 쳐서 식의 최댓값을 구하는 문제다.

예시 1

1 - 3 + 5 - 8 이라면
1 - ( 3 + ( 5 - 8 ) ) 이렇게 괄호를 쳤을 때 최댓값이 1이 나오고,

예시 2

5 - 3 + 1 + 2 - 4 라면
5 - ( 3 + 1 + 2 - 4 ) 이렇게 괄호를 쳐서 최댓값이 3 이 나온다.

---

해결 아이디어

괄호를 어떻게 치든, 결국 식은 어떤 구간을 먼저 계산해서 합치는 형태이다.

그래서 구간 DP로 접근한다.

• maxDP[i][j] : nums[i] ~ nums[j] 구간으로 만들 수 있는 최댓값
• minDP[i][j] : 같은 구간의 최솟값

왜 minDP가 필요한가요?

A - B에서 최댓값을 만들려면 '-' 다음 오는 B가 작아야 한다.
즉, A - (오른쪽 구간)에서 오른쪽 구간의 최솟값이 필요하기 때문에 최솟값 DP 배열이 필요하다.

식과 식 사이의 연산자 (+ or -) 가 무엇이냐에 따른 최댓값, 최소값 구하는 방식

• + : 최댓값 = 최대 + 최대 / 최솟값 = 최소 + 최소
• - : 최댓값 = 최대 - 최소 / 최솟값 = 최소 - 최대

이 규칙이 핵심이다.

해답 및 풀이

# arr = ["1", "-", "3", "+", "5", "-", "8"]
# arr = ["5", "-", "3", "+", "1", "+", "2", "-", "4"]
def solution(arr):
    # 1) 토큰 분리: nums, ops
    
    nums = []
    ops = []
    
    for token in arr:
        if token == "+" or token == "-":
            ops.append(token)
        else:
            nums.append(int(token))
    
    n = len(nums)
    INF = float('inf')
    
    
    # 2) DP 테이블
    # dp[i][j] = 배열의 인덱스 i~j 구간의 최댓값 or 최솟값 
    maxDP = [[-INF] * n for _ in range(n)]
    minDP = [[INF] * n for _ in range(n)]
    
    # 3) 길이 1 dp는 자기 자신
    for i in range(n):
        maxDP[i][i] = nums[i]
        minDP[i][i] = nums[i]
        
    # 4) 구간 길이를 늘려가며 채우기
    # length = 2 ... n
    for length in range(2, n + 1): # length 지금 계산할 "구간 길이"
        for i in range(0, n - length + 1): # i 구간의 시작 인덱스
            j = i + length - 1 # j 구간의 끝 인덱스, length.= 끝 - 처음 + 1
        
        # i...j 구간을 i..k, k+1..j 로, k 를 기준으로 좌,우 두개의 식으로 나누기
            for k in range(i,j):
                op = ops[k] # ops[0]은 nums[0]과 nums[1] 사이 연산자
            
                if op == "+":
                    # 최대 = 최대 + 최대
                    maxDP[i][j] = max(maxDP[i][j], maxDP[i][k] + maxDP[k+1][j])
                    # 최소 = 최소 + 최소
                    minDP[i][j] = min(minDP[i][j], minDP[i][k] + minDP[k+1][j])
                elif op == "-":
                    # 최대 = 최대 - 최소
                    maxDP[i][j] = max(maxDP[i][j], maxDP[i][k] - minDP[k+1][j])
                    # 최소 = 최소 - 최대
                    minDP[i][j] = min(minDP[i][j], minDP[i][k] - maxDP[k+1][j])

    return maxDP[0][-1]