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

두 가지 풀이법이 있습니다.

 

1. dp 방법입니다.

펄스는 짝수, 홀수에 따라 1 또는 -1이 반복됩니다.

주어지는 sequence에 펄스를 곱한 값의 최대를 dp에 저장시켜 값을 갱신하면 됩니다.

 

2. 누적합 방법입니다.

펄스를 곱한 값을 누적합하고, 누적합의 최대 위치가 연속된 부분 수열의 마지막 원소 위치가 됩니다.

예를 들어 펄스를 곱한 배열이 [8, -1, -7, -100, 55, 40, 13]있다고 하겠습니다.

여기서 최대 부분 수열은 [55, 40, 13]입니다.

배열을 누적합하면 [8, 7, 0, -100, -45, -5, 8] 입니다.

누접합의 가장 큰 원소가 8이고, 해당 배열에서 위치의 값은 13입니다. 

13 위치에서 부터 뒤로 원소를 끝까지 확인하면서 최대 값을 구하면 됩니다.

단, 문제 통과는 되지만 dp의 방법보다 시간이 오래 걸립니다.

 

[구현 코드 - dp]

import java.util.*;

class Solution {
    public long solution(int[] sequence) {
        long answer = Long.MIN_VALUE;
        
        int n = sequence.length;
        
        // 0 : [-1, 1, -1, 1, ...]
        // 1 : [1, -1, 1, -1, ...]
        // sequence와 pulse를 곱한 dp을 저장함
        List<long[]> dps = List.of(new long[n], new long[n]);
        
        dps.get(0)[0] = pulseMultiNumber(0, 0, sequence);
        dps.get(1)[0] = pulseMultiNumber(1, 0, sequence);
        answer = Math.max(dps.get(0)[0], dps.get(1)[0]);
        
        for(int i=1; i<n; i++){
            for(int k=0; k<2; k++){
                long cal = pulseMultiNumber(k, i, sequence);
                dps.get(k)[i] = Math.max(cal, dps.get(k)[i-1] + cal);
            }
            answer = Math.max(answer, Math.max(dps.get(0)[i], dps.get(1)[i]));
        }
        
        return answer;
    }
    
    private long pulseMultiNumber(int k, int i, int[] sequence){
        long t;
        if(i % 2 == 0) { // 짝수
            t = (k == 0) ? (sequence[i] * -1) : sequence[i];
        } else { // 홀수
            t = (k == 0) ? sequence[i] : (sequence[i] * -1);
        }
        return t;
    }
}

 

[구현 코드 - 누적합]

import java.util.*;

class Solution {
    public long solution(int[] sequence) {
        long answer = Long.MIN_VALUE;
        
        int n = sequence.length;
        
        // 0 : [-1, 1, -1, 1, ...]
        // 1 : [1, -1, 1, -1, ...]
        // sequence와 pulse를 곱한 순열 '누접합'을 저장함
        List<long[]> pres = List.of(new long[n], new long[n]);
        
        // 누적합의 최대 위치를 저장함
        List<List<Integer>> locations = new ArrayList<>();
        
        for(int k=0; k<2; k++){    
            long[] pre = pres.get(k); // 누적합 할 배열
            pre[0] = pulseMultiNumber(k, 0, sequence);
            
            long maxValue = pre[0];
            int maxLocation = 0;
            List<Integer> maxs = new ArrayList<>();
            maxs.add(maxLocation);
            
            for(int i=1; i<n; i++){
                long t = pulseMultiNumber(k, i, sequence);
                pre[i] += (pre[i-1] + t); // 누적합
                    
                if(maxValue < pre[i]){ // 누적합의 최대 위치 저장
                    maxValue = pre[i];
                    maxLocation = i;
                    maxs = new ArrayList<>();
                    maxs.add(maxLocation);
                }else if(maxValue == pre[i]){
                    maxs.add(i);
                }
            }
            
            locations.add(maxs);
        }
        
        for(int k=0; k<2; k++){    
            long[] pre = pres.get(k);
            List<Integer> los = locations.get(k);
            
            // 저장된 누적합의 최대 위치부터 좌로 가면서 부분 수열의 합 중 가장 큰 것를 구함
            for(int lo : los){
                long sum = 0;
                long t = 0;
                for(int i=lo; i>=0; i--){
                    sum += pulseMultiNumber(k, i, sequence);
                    answer = Math.max(answer, sum);
                }
            }
        }
        
        return answer;
    }
    
    private long pulseMultiNumber(int k, int i, int[] sequence){
        long t;
        if(i % 2 == 0) { // 짝수
            t = (k == 0) ? (sequence[i] * -1) : sequence[i];
        } else { // 홀수
            t = (k == 0) ? sequence[i] : (sequence[i] * -1);
        }
        return t;
    }
}