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

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

프로그래머스

문제 설명

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

제한 사항

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

정답 설명

연속 부분 수열의 합을 계산하는 문제이므로, 누적합 배열을 사용하면 쉽게 답을 구할 수 있다.

누적합 배열이 처음이거나, 익숙하지 않다면 블로그에 포스팅 해 둔 글을 링크해 둘테니, 참고 바란다.

https://zangsu.tistory.com/4

[Algorithm] 누적 합

 

이 문제 해결의 핵심은 누적합 배열에서 특정 연속 부분 배열의 합을 구하는 방식이다.

기존의 누적합 배열에서 특정 연속 부분 배열의 합을 구하는 방법은 누적합 배열의 원소 두개를 빼는 것이다.

조금 더 자세히 알아보자.

누적합 배열의 i번째 원소는 특정 배열의 0번째 원소부터 i번째 원소까지의 모든 합을 저장한 것이다.

만약 우리에게 0번째부터가 아닌, j번째 원소부터 i번째 원소까지의 합이 필요하다고 가정하자. 그렇다면 우리는 누적합 배열의 i번째 원소에서 누적합 배열의 j-1번째 원소를 빼 j~i 구간의 누적 합을 구할 수 있다.

 

이번 문제에서 사실 우리에게는 두개의 누적합 배열이 필요하다. 원 배열의 펄스 배열은 원 배열에 [1, -1, 1, ...]을 곱한 배열과 [-1, 1, -1, ...]을 곱한 배열의 두가지 경우가 존재하기 때문이다.

그러나, 사실 두 배열의 수는 부호만 다른 같은 수이며, 때문에 두 펄스 배열에서 구할 수 있는 누적합 배열 역시 서로 부호만 다른 같은 배열이다.

 

A 배열을 원 배열에서 [1, -1, 1, ...]을 곱한 펄스 배열의 누적합 배열, B 배열을 원 배열에서 [-1, 1, -1, ...]을 곱한 펄스 배열의 누적합 배열이라고 하자.

이 때, 원 배열에서 [1, -1, 1, ...]을 곱한 펄스 배열에서 j~i 구간의 원소들의 누적합 배열은 A 배열의 i번째 원소에서 A 배열의 j-1번째 원소를 뺀 값이다. 그런데, 이 값은 B 배열에서도 구할 수 있는데, 그 식은 -(B[i] - B[j]) = B[j] - B[i] 이다.

즉, 하나의 펄스 배열에 대한 누적합 배열로도 두가지 펄스 배열의 누적합을 모두 구할 수 있는 것이다.

 

이제 우리는 두 펄스 배열중 하나의 펄스 배열에 대해 누적합 배열을 구한다. 그리고, 누적합 배열의 최댓값에서 누적합 배열의 최솟값을 빼 주는 연산을 통해 연속 펄스 부분 배열의 합 중 가장 큰 값을 구할 수 있다.

 

(만약 누적합 배열의 최댓값의 인덱스 i보다 최솟값의 인덱스 j가 크다고 가정하자. 이 때는 우리는 A[i] - A[j]처럼 누적합 배열의 앞에 위치한 값에서 뒤에 위치한 값을 빼는 형태가 된다. 반복하지만, 이러한 연산이 가능한 이유는 우리에게 부호만 다른 두가지 누적합 배열이 필요하기 때문이다. A[i] - A[j]의 값은 - (A[j] - A[i]) 와 같으며, 이는 우리가 고려하지 않은 나머지 펄스 배열에서 구할 수 있는 최댓값과 같다.)

 

소스 코드

import java.util.*;
class Solution {
    public long solution(int[] sequence) {
        
        long[] prefixSum = new long[sequence.length + 1];
        long max = 0;
        long min = 0;
        for(int i = 0; i<sequence.length; i++){
            if(i % 2 == 1)
                sequence[i] *= -1;
            prefixSum[i+1] = prefixSum[i] + sequence[i];
            if(max < prefixSum[i+1])
                max = prefixSum[i+1];
            if(min > prefixSum[i+1])
                min = prefixSum[i+1];
        }        
        return max - min;        
    }
}