[프로그래머스] 161988 - 연속 펄스 부분

https://school.programmers.co.kr/learn/courses/30/lessons/161988

문제 파악

어려운 점

• 변수 type 신경쓰기 (int, long)
• DP 의미(?) 유지하기
  • DP를 업데이트 해 나가면서 이것 저것 덧붙이려는 자신을 볼 수 있다.
    일관성을 유지하도록 하자

풀이

2차원 DP(int[][] DP)로 해결

DP에서의 더해주고 빼는 행위를 0번째 열, 1번째 열에 저장하여 구현하면 편할 듯 했다.

[구현 순서]

1. 초항 초기화(N-1번째 값)
2. N-1번째 부터 0번째에서 순서대로 memorization을 진행

 

DP[i] 데이터를 업데이트하는 방법은 다음과 같다.

• 주어진 수(sequence[i])에 -를 곱하는 경우(=펄스 부분 수열에서 -1)를 DP[i][0]에 업데이트
• 주어진 수(sequence[i])를 그대로 활용하는 경우((=펄스 부분 수열에서 +1)를 DP[i][1]에 업데이트

업데이트를 해 주면서 DP[i][0], DP[i][1] 중 가장 큰 값을 저장하여 정답으로 리턴하자.

 

sequence[i]번째 데이터를 빼버리는 실수는 하지 말자😊
이는 i-1번째 데이터가 쓸 유용한 값이다 😇

 

DP[i][0]의 경우 1️⃣DP[i+1][1]의 값을 활용하거나, 2️⃣ 활용하지 않을 수 있다
2️⃣ 활용하지 않는다의 경우는 DP[i+1][1]가 음수일 경우일 것이다. 

DP[i][1]의 경우도 마찬가지이다.
DP[i][1]의 경우 1️⃣DP[i+1][0]의 값을 활용하거나, 2️⃣ 활용하지 않을 수 있다
2️⃣ 활용하지 않는다의 경우는 DP[i+1][0]가 음수일 경우이다.

 

코드

public class Solution {
    public long solution(int[] sequence) {
        if (sequence.length == 1) {
            return Math.abs(sequence[0]);
        }
        long[][] dp = new long[sequence.length][2];
        // 0 index col ) * -1
        // 1 index col ) * +1
        dp[sequence.length - 1][0] -= sequence[sequence.length - 1];
        dp[sequence.length - 1][1] += sequence[sequence.length - 1];
        long max = Long.MIN_VALUE;
        for (int i = dp.length - 2; i >= 0; i--) {
            dp[i][0] = Math.max(0, dp[i + 1][1]) - sequence[i];
            dp[i][1] = Math.max(0, dp[i + 1][0]) + sequence[i];
            max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
        }
        return max;
    }
}