[프로그래머스] 연속 펄스 부분수열의 합

문제

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다.

펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다.

또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

풀이

합이 최고가 되는 펄스 수열을 구해야 한다.
처음에는 누적합을 생각했는데 그러면 모든 경우를 다 고려해야 하므로 시간 초과가 날 것이라고 판단하였다.

DP를 생각하였는데 DP[i][K]라고 할 때 이는 i번째에서 최고가 되는 부분 펄스 수열이라고 하자.
이때 K는 0과 1로 나뉘는데 이는 각 -1로 시작하는 펄스 수열과 1로 시작하는 펄스 수열이라고 생각하자.

따라서 점화식을 세우면
MAX(dp[i][0] = MAX(arr[i], dp[i][1] + arr[i]), dp[i][1] = MAX(-arr[i], dp[i][0] - arr[i]))가 된다.

import java.util.*;
import java.lang.*;

class Solution {
    public long solution(int[] sequence) {
        int N = sequence.length;
        long[][] dp = new long[N][2];

        dp[0][0] = sequence[0];
        dp[0][1] = sequence[0] * -1;

        long max = Math.max(dp[0][0], dp[0][1]);

        for(int i = 1; i < N; i++) {
            dp[i][0] = Math.max(sequence[i], dp[i - 1][1] + sequence[i]);
            dp[i][1] = Math.max(sequence[i] * -1, dp[i - 1][0] - sequence[i]);
            max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
        }

        return max;
    }
}

https://github.com/Win-9/Algorism/blob/main/programers/%EC%97%B0%EC%86%8D%20%ED%8E%84%EC%8A%A4%20%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4%EC%9D%98%20%ED%95%A9/Solutaion.java