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

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

난이도

Level 3

문제

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

내 코드

class Solution {
    public long solution(int[] sequence) {
        int[] pulse1 = new int[sequence.length];
        int[] pulse2 = new int[sequence.length];
        
        for(int i = 0; i < sequence.length; i++){
            pulse1[i] = sequence[i] * (i % 2 == 0 ? 1 : -1);
            pulse2[i] = sequence[i] * (i % 2 == 0 ? -1 : 1);
        }
        
        long max1 = getMax(pulse1);
        long max2 = getMax(pulse2);
        return Math.max(max1, max2);
    }
    
    public long getMax(int[] pulse){
        long maxSum = pulse[0];
        long currentSum = pulse[0];
        
        for(int i = 1; i < pulse.length; i++){
            currentSum = Math.max(pulse[i], currentSum + pulse[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

이 문제는 주어진 수열 sequence에서 펄스 수열(1, -1, 1, -1...)을 곱한 결과 중 연속된 부분 수열의 합이 가장 큰 경우를 찾는 문제이다.

즉, +1, -1, +1... 혹은 -1, +1, -1...의 형태로 펄스를 번갈아 곱했을 때 만들어지는 두 수열 각각에서 최대 부분 수열 합을 구하고, 그 중 더 큰 값을 반환해야한다.

여기서 핵심은 부분 수열이 연속되어야 한다는 조건이다. 이는 일반적인 누적합이나 브루트포스 방식으로 해결하면 시간 복잡도가 커지기 때문에, O(N) 시간에 처리 가능한 Kadane’s Algorithm을 적용할 수 있다.

Kadane’s Algorithm

1. 현재 위치까지의 최대합을 저장하는 변수 currentSum을 유지한다.
2. 각 원소를 보면서, 이전까지의 합 + 현재 값과 현재 값 중 더 큰 값을 선택한다. 이는 이전 구간을 이어갈지, 새로 시작할지를 결정하는 과정이다
3. 그 중 가장 큰 값을 maxSum으로 갱신한다.

이 과정을 배열의 처음부터 끝까지 반복하면 가장 큰 연속된 구간의 합을 찾을 수 있다.