[PRG] 161988 연속 펄스 부분 수열의 합 JAVA

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

프로그래머스

 

메모리: 132 MB

실행시간: 14.07 ms

 

문제 분석

배열 길이가 최대 50만이므로, N(nlogn) 안에 해결해야 한다.
부분 수열의 합을 알아내는 문제이므로
누적합을 활용해 풀어보자 !

 

걸린 시간

40분 ⏱️

 

풀이 방법

1. 누적합 배열을 만든다.
2. 누적합으로 저장하면서 최대합과 최저합을 구한다.
3. 최대합 - 최소합을 리턴한다.

 

포인트

0	2	-3	-6	-1	3	1	2	-4    -----> [1, -1, 1, ...] 을 곱한 배열
-------------------------------------------------------------------
0	2	-1	-7	-8	-5	-4	-2	-6    -----> 위 배열의 누적합




0	-2	3	6	1	-3	-1	-2	4     -----> [-1, 1, -1, ...] 을 곱한 배열
-------------------------------------------------------------------
0	-2	1	7	8	5	4	2	6     -----> 위 배열의 누적합


두 개의 누적합 배열을 보면, 부호만 반대인 것을 알 수 있다.
따라서 한 가지의 배열만 구한 뒤, 최대합 - 최소합을 구하면 된다 !

 

코드

class Solution {
    public long solution(int[] sequence) {
        
        // 누적합 배열 만들기 
        long[] prefix = new long[sequence.length + 1];
        long maxSum = 0;    // 최대합
        long minSum = 0;    // 최소합

        for(int i = 0; i < sequence.length; i ++) {
            // 누적합으로 저장
            if(i % 2 == 0) {
                prefix[i + 1] = sequence[i] + prefix[i];
            } else {
                prefix[i + 1] = sequence[i] * -1 + prefix[i];
            }
            maxSum = Math.max(maxSum, prefix[i + 1]);   // 최대합 저장
            minSum = Math.min(minSum, prefix[i + 1]);   // 최소합 저장
        }
        
        return maxSum - minSum;
    }
}