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

피나코·2023년 3월 28일

알고리즘

목록 보기

45/46

프로그래머스_연속 펄스 부분 수열의 합 바로가기

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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 함수를 완성해주세요.

접근 방식

펄스 수열(2가지)을 적용한 배열에서, 다이나믹 프로그래밍을 활용하여 최대 부분 수열의 합을 구했다.

최대 부분 수열의 합은 Kadane's 알고리즘을 이용해서 풀었다.

전 단계 까지의 부분 수열의 합 최대값에 현재의 수열의 값을 더한것과 현재 수열의 값 중 큰 값을 DP[i]로 하는 점화식이다.

시간복잡도가 O(N)이기에 주어진 범위에도 시간초과가 발생하지 않을것이다.

코드

class Solution {
    public long solution(int[] sequence) {
        long answer = 0L;

        int sequenceLength = sequence.length;

        for (int i = 0; i < sequenceLength; i++) {
            sequence[i] = (int) (sequence[i] * Math.pow(-1, (i & 1)));
        }

        long[] dp = new long[sequenceLength];
        dp[0] = sequence[0];
        answer = Math.max(dp[0], answer);

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

        for (int i = 0; i < sequenceLength; i++) {
            sequence[i] = (int) (sequence[i] * Math.pow(-1, (i & 1)));
        }
        for (int i = 0; i < sequenceLength; i++) {
            sequence[i] = (int) (sequence[i] * Math.pow(-1, ((i + 1) & 1)));
        }

        dp = new long[sequenceLength];
        dp[0] = sequence[0];
        answer = Math.max(dp[0], answer);

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

        return answer;
    }
}