[Lv.3] 연속 펄스 부분 수열의 합

50/100 (메모리 초과)

class Solution {
    public long solution(int[] sequence) {
        int size= sequence.length;
        long[][][] dp=new long[size+1][size+1][2];
        //i~i까지 dp
        //0: -1, 1:1 start
        long answer=Integer.MIN_VALUE;
        
        for(int i=0;i<size;i++){
            dp[i][i][0]=sequence[i]*-1;
            dp[i][i][1]=sequence[i];
            answer=Math.max(Math.max(dp[i][i][0],dp[i][i][1]),answer);
        }
        for(int i=1;i<size;i++){
            //윈도우 크기
            for(int j=0;j<size-i;j++){
                //탐색 시작 인덱스 값
                if(i%2==1){
                    //i=1,3 ..-> 2칸,4칸 .. -> j~[j+i-1][0]+ j+i j+i [1] or dp[j][j][0]+ j+1 j+i [1]                
                    dp[j][j+i][0]=Math.max(dp[j][j+i-1][0]+dp[j+i][j+i][1],dp[j][j][0]+dp[j+1][j+i][1]);
                    dp[j][j+i][1]=Math.max(dp[j][j+i-1][1]+dp[j+i][j+i][0],dp[j][j][1]+dp[j+1][j+i][0]);
                }else{
                    //i=2,4 ->3칸 5칸 ->
                    dp[j][j+i][0]=Math.max(dp[j][j+i-1][0]+dp[j+i][j+i][0],dp[j][j][0]+dp[j+1][j+i][1]);
                    dp[j][j+i][1]=Math.max(dp[j][j+i-1][1]+dp[j+i][j+i][1],dp[j][j][1]+dp[j+1][j+i][0]);
                }
                answer=Math.max(Math.max(dp[j][j+i][0],dp[j][j+i][1]),answer);
                
            }
        }        
        return answer;    
    }
}

정답코드

class Solution {
    public long solution(int[] sequence) {
        int size= sequence.length;
        long[][] dp=new long[size+1][2];
        // i번 까지의 dp값
        //0: -1, 1:1 (수열 시작 값)
        //즉 dp[i][0]는 0번째 인덱스에 -1을 곱해서 i번째 까지 온 수의 최대
        // i 1은 0번째 인덱스에 1을 곱해서 i번째 까지 온 수의 최대
        long answer=Integer.MIN_VALUE;
        
        dp[0][0]=sequence[0]*-1;
        dp[0][1]=sequence[0];
        answer=Math.max(dp[0][0],dp[0][1]);
        
        
        for(int i=1;i<size;i++){
            //윈도우 크기
            if(i%2==1){
                //i=3 -> 1 -1 1 (-1) / -1 1 -1 1
                dp[i][0]=Math.max(dp[i-1][0]+sequence[i],sequence[i]);
                dp[i][1]=Math.max(dp[i-1][1]+sequence[i]*-1,sequence[i]*-1);
            }else{
                //i=2 -> 1 -1 1, -1 1 -1
                dp[i][0]=Math.max(dp[i-1][0]+sequence[i]*-1,sequence[i]*-1);
                dp[i][1]=Math.max(dp[i-1][1]+sequence[i],sequence[i]);
            }
            answer=Math.max(Math.max(dp[i][0],dp[i][1]),answer);                
        }        
        return answer;    
    }
}

처음에 dp로 풀어야겠다고 생각하고 3차원배열로 풀었더니 메모리초과가 났다.

(물론, for-loop을 2번돌았기에 어차피 시간초과도 났을 것이다..)

메모리초과라는 오류덕에 2차원 dp로 풀 방법이 있다고 생각이 들었고

기존엔 i~j까지의 sequence에 -1,1을 곱한 값의 최대를 구하는 dp를 정의했고, 기존 dp값 앞,뒤에 값을 더한 값 중 더 큰 값을 새로운 dp값으로 하는 for-loop을 돌며 최댓값을 찾았다.

정답일지언정 메모리가 나가고 반복문도 많이도니 이 방식으론 정답을 맞출 수 없다.

 

2차원 dp로 푸는 방법은, "연속된"에 주목하여 첫번째 인덱스의 의미를 i번째 수까지의 최대 펄스 수열 합이라고 생각하는 것이다.

즉, 0번째 수까지의 최대 값을 미리 init하고 1번째 수를 포함한 펄스 수열 합과 1번째 수부터 새로 시작하는 펄스 수열 합 중 가장 큰 값을 dp[1]로 하고 이 과정을 반복하는 것이다.

 

또, 2번째 인덱스의 의미는 0인 경우 0번째 인덱스에 -1을 곱하는 수열, 1은 1을 곱하는 펄스 수열을 의미한다.

 

문제 자체는 기본적인 dp문제라고 생각된다..

다만, 단번에 2차원으로 풀 방법을 떠올리지 못해 3차원으로 시도했다는 점이 아쉬웠다.