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

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

접근

sequence 의 길이 제한이 $1\leq{...}\leq{500,000}$ 이므로 $O(N^2)$ 이상의 시간 복잡도를 가지는 알고리즘으로 문제를 해결할 수 없다.

연속 펄스 부분 수열의 합의 최댓값을 구하는 것이므로 펄스 수열을 DP에 대응시켜 문제를 해결할 수 있다.

즉, sequence 를 iteration 하면서 현재 원소와 이전의 연속 펄스 부분 수열의 합과 비교해 더 큰 값을 계속해서 저장시킨다.

단, 펄스 수열이 -1과 1 두 가지 경우로 시작할 수 있으므로 두 경우 모두 저장시키도록 DP 배열을 정의한다.

dp[i][0] : sequence 의 인덱스 0부터 i까지 펄스 수열의 양수에 대응하는 연속 펄스 부분 수열의 합의 최댓값

dp[i][1] : sequence 의 인덱스 0부터 i까지 펄스 수열의 음수에 대응하는 연속 펄스 부분 수열의 합의 최댓값

소스코드(Java)

class Solution {
    public long solution(int[] sequence) {
        long[][] dp = new long[sequence.length][2];
        long max = -1;
        dp[0][0] = sequence[0];
        dp[0][1] = -sequence[0];
        max = Math.max(dp[0][0], dp[0][1]);
        for(int i = 1; i < sequence.length; i++) {
            dp[i][0] = Math.max(sequence[i], dp[i-1][1] + sequence[i]);
            dp[i][1] = Math.max(-sequence[i], dp[i-1][0] - sequence[i]);
            max = Math.max(max, dp[i][0]);
            max = Math.max(max, dp[i][1]);
        }

        return max;
    }
}