문제 설명

5-3+1+2-4 같은 문자열 배열이 주어지면, 이 연산의 최댓값 구하기, 단 연산은 +와 -밖에 없다.

문제 접근

처음에 dp로 접근은 했으나, -의 소비 개수를 따라 선형적으로 한 번만 읽고 지나가며 구하려고 했다. 하지만, 구현이 쉽지 않았고 생각보다 중복을 많이 제거 못한다는 것을 깨닫고 철회했다.
어떻게 점화식을 세울지 고민해보다 결국은 질문게시판에서 힌트를 보고 풀었다.
참고한 링크는 다음과 같다. 접근법부터 상세하게 설명해주셔서 좋았다.
https://school.programmers.co.kr/questions/35224

우선, 숫자들만 따로 추출해서 바라본다. s~e번까지의 숫자들의 부분합의 최대와 최소를 각각 구하고 기억하면 된다. 그리고 필요할때 각 구간의 최대 혹은 최소합을 구했던걸 그대로 돌려주면 된다.
범위(여기서 범위란 s~e사이의 크기)를 1부터 시작해서 n-1까지 넓혀가며 각 숫자들 간 최댓,최솟 합을 구해준다.
=> 이렇게 할 수 있는 이유는 어차피 연산이라는 것은 순차적으로 이웃한 녀석들끼리만 가능하기 때문임.

그리고, 이 문제를 풀 때 두번째로 중요한 개념도 있다. 분할 정복을 떠올려서 이 문제의 근본적인 문제를 축소시켜서 고민해야 한다.

• a+b 는
  a와 b의 최댓값의 합이 최댓값임.
  a와b의 최솟값이 최솟값임.
• a-b는
  a최댓값,b최솟값이 최댓값임,
  a최솟값,b최댓값이 최솟값임

풀이

import java.util.*;
import java.io.*;

class Solution {
    int n;
    String[] arr;
    int[] numbers;
    int[][] maxDp;
    int[][] minDp;
    
    final int MAX_VALUE = 10_0000_0000;
    final int MIN_VALUE = -10_0000_0000;    
    
    public int solution(String arr[]) {
        this.arr = arr;
        this.n = arr.length / 2 + 1;
        maxDp = new int[n][n];
        minDp = new int[n][n];  
        numbers = new int[n];
        for(int i = 0; i<n; i++) {
            numbers[i] = Integer.parseInt(arr[i*2]);
            Arrays.fill(maxDp[i], MIN_VALUE);
            Arrays.fill(minDp[i], MAX_VALUE);
        } 
        
        for(int range = 1; range<= n; range++) {
            int s=0;
            int e=s+range-1;
            for(; e<n; s++, e++) {
                rangeSum(s,e,true);
            }
        }
        
        return maxDp[0][n-1];
    }
    
    // isMax는 반환값을 결정할 뿐임. s~e 사이를 포함한 연산의 최대,최소 결과는 둘 다 구한다.
    int rangeSum(int s, int e, boolean isMax) {
        if (isMax && maxDp[s][e] != MIN_VALUE) return maxDp[s][e];
        if (!isMax && minDp[s][e] != MAX_VALUE) return minDp[s][e];
        
        int rangeSize = e-s+1;
        if (s==e) {
            maxDp[s][e] = numbers[s];
            minDp[s][e] = numbers[s];            
            return numbers[s];
        } else if (s+1 == e){
            if (arr[s*2 + 1].equals("-")){
                maxDp[s][e] = numbers[s] - numbers[e];
                minDp[s][e] = numbers[s] - numbers[e];                
                return numbers[s] - numbers[e];
            } else {
                maxDp[s][e] = numbers[s] + numbers[e];
                minDp[s][e] = numbers[s] + numbers[e];                  
                return numbers[s] + numbers[e];               
            }
        } else {
            int j = 0;
            for (int i=1; i<rangeSize; i++) {
                j = rangeSize - i;
                if(arr[(s+i-1)*2 + 1].equals("+")) {
                    maxDp[s][e] = Math.max(maxDp[s][e], rangeSum(s, s+i-1, true) + rangeSum(s+i, e, true));
                    minDp[s][e] = Math.min(minDp[s][e], rangeSum(s, s+i-1, false) + rangeSum(s+i, e, false));
                } else {
                    maxDp[s][e] = Math.max(maxDp[s][e], rangeSum(s, s+i-1, true) - rangeSum(s+i, e, false));
                    minDp[s][e] = Math.min(minDp[s][e], rangeSum(s, s+i-1, false) - rangeSum(s+i, e, true));                    
                }
            }
            
            if (isMax) {
                return maxDp[s][e];
            } else {
                return minDp[s][e];                
            }
        }
    }
 
}

자바로 풀때, 스트링 비교는 equals 잊지말자.
그리고 dp는 문제 성격에 따라 최솟값과 최댓값을 함께 트래킹 해야할 필요도 있을 수 있다.