[Programmers] 연속 펄스 부분 수열의 합 (Java)

1.  문제 링크

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

2.  문제

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

3.  제한사항

• 1 ≤ sequence의 길이 ≤ 500,000
• -100,000 ≤ sequence의 원소 ≤ 100,000
  • sequence의 원소는 정수입니다.

입출력 예

4.  소스코드

class Solution {
    public long solution(int[] sequence) {
        long[] prefixSum = new long[sequence.length + 1];
        long[] prefixSum2 = new long[sequence.length + 1];

        for(int idx = 1; idx <= sequence.length; idx++) {
            if(idx % 2 == 0)
                prefixSum[idx] = prefixSum[idx - 1] + sequence[idx - 1];
            else
                prefixSum[idx] = prefixSum[idx - 1] + sequence[idx - 1] * (-1);
        }

        for(int idx = 1; idx <= sequence.length; idx++) {
            if(idx % 2 == 0)
                prefixSum2[idx] = prefixSum2[idx - 1] + sequence[idx - 1] * (-1);
            else
                prefixSum2[idx] = prefixSum2[idx - 1] + sequence[idx - 1];
        }

        long max1 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE;
        long max2 = Integer.MIN_VALUE, min2 = Integer.MAX_VALUE;
        for(int idx = 0; idx < prefixSum.length; idx++) {
            max1 = Math.max(max1, prefixSum[idx]);
            min1 = Math.min(min1, prefixSum[idx]);

            max2 = Math.max(max2, prefixSum2[idx]);
            min2 = Math.min(min2, prefixSum2[idx]);
        }

        long max = Math.max(max1 - min1, max2 - min2);

        return max;
    }
}

5.  접근

• [1, -1, 1, -1, ...] 펄스 수열과 곱하여 만든 수열의 누적 합을 prefixSum 배열에 저장하고 [-1, 1, -1, 1, ...] 펄스 수열과 곱하여 만든 수열의 누적 합을 prefixSum2 배열에 저장합니다.
• 누적합을 통해 각 부분 수열의 합을 알 수 있는데, 이 때 합이 가장 큰 부분 수열의 합은 누적합에서 최대값과 최소값을 뺀 부분이 가장 큰 부분 수열이 될 것이고, 최대값과 최소값을 뺀 값이 가장 큰 부분 수열의 합이 될 것입니다.
• 그렇기 때문에 prefixSum, prefixSum2 두 누적 합에서 최대값과 최소값을 각각 찾습니다.
• 이후에 각각 최대값에서 최소값을 뺀 값을 구하고 두 값 중 큰 값을 반환합니다.