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

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

프로그래머스

 

문제 설명

이 문제는 부분 수열의 최대 합을 구하는 문제와 엄청 유사합니다. 다른 점은 펄스 수열을 곱한 부분 수열의 최대 합을 구하는 것입니다. 

 

문제에 대한 아이디어

부분 수열의 합을 구하는 방법은 DFS를 통해 모든 경우를 조사해서 최대 합을 찾는 방법이 존재합니다. 하지만 이 문제에서는

최대 500000개 이므로 DFS로 탐색하면 시간 초과가 나올 것입니다. 그러므로 O(n) 안에 풀어야 합니다.

 

펄스 수열 처리

펄스 수열 처리는 간단합니다. 부분 수열에 펄스 수열을 곱할 생각을 하지 말고 애초에 펄스 수열을 곱한 2개의 수열을 만드는 것입니다

• [1, -1, 1, -1, 1, -1, 1,...] 
• [-1, 1, -1, 1, -1, 1, -1, ...]

이 배열을 곱한 배열을 각각 구현합니다.

 

부분 수열의 최대합 구하기

O(n) 안에 풀기 위해서는 sequence를 한 번만 순회하면서 문제를 해결해야 합니다.

제가 생각한 방법은 지금까지의 합에서 지금까지의 수중 합의 최솟값을 빼는 것입니다.

예를 들어 [-2, 3, 6, 1] 이면 지금 까지 합은 8이고 이 중 만들 수 있는 합의 최솟값은 -2이므로 -2를 빼주는 것 입니다.

 

전체 코드

class Solution {
    public long solution(int[] sequence) {
        long answer = Long.MIN_VALUE;
        // 수열 2개 만듬
        int[] temp_seq1 = new int[sequence.length]; 
        int[] temp_seq2 = new int[sequence.length];
        for(int i = 0; i < sequence.length; ++i){
            temp_seq1[i] = sequence[i] * (int) Math.pow(-1,i);
            temp_seq2[i] = sequence[i] * (int) Math.pow(-1,i+1);
        } 
        long sum1 = temp_seq1[0]; long sum2 = temp_seq2[0]; // 첫번째 수
        long min1 = 0; long min2 = 0;
        for(int i = 1; i < sequence.length; ++i){
            // 지금 까지 더한 수 중 최솟값 선택
            min1 = Math.min(sum1, min1); 
            min2 = Math.min(sum2, min2);
            
            // 지금 까지 의 합 중 최솟값 뺌
            answer = Math.max(answer, Math.max(sum1-min1,sum2-min2));   
            
            // 합 구하기
            sum1 += temp_seq1[i];
            sum2 += temp_seq2[i];
        }
        // 마지막 합 조사하기
        answer = Math.max(answer, Math.max(sum1-min1,sum2-min2));   
        return answer;
    }
}