[프로그래머스] 연속 펄스 부분 수열의 합 (자바)

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

프로그래머스

 

 

 

문제 

 

펄스 수열은 두가지 종류가 있고 [1, -1, 1 -1, 1.... ] [-1, 1, -1, 1....] 

펄스 수열을 곱한 연속된 수열에서 연속된 값의 합이 최대가 되는 숫자를 구하는 문제 이다. 

 

펄스 수열을 구해야하는 문제와, 연속된 수열의 합을 구하는 부분을 따로 생각해보면 

 

---

1. 펄스 수열을 적용하는 부분 

펄스 수열을 적용한 수열은 결국 두 가지 수열밖에 나타나지 않는다. 

 

예시의 수열을 살펴보면 

 

[2, 3, -6, 1, 3, -1, 2, 4] => [-2, 3, 6, 1, -3, -1, -2, 4] 혹은 [2, -3, -6, -1, 3, 1, 2, -4]  

 

몇 번째 요소에서 시작하든 수열은 이 두가지 경우의 수밖에 나오지 않는다. 

 

 

2. 연속된 합이 최대가 되는 값

수열은 연속되어야 하고, 그 합이 최대가 되어야 한다.

연속되어야 하는 제약사항이 있지만 결국 다이나믹 프로그래밍으로 해결할 수 있다. 

 

dp[n] 을 n 번째 숫자를 포함한 최대값이라고 지정하고 점화식을 만들 수 있다. 

dp[n] = Max( dp[n-1] + n , n )

 

n 번째 숫자를 포함할 때 그 합이 최대가 되는 경우는,

이전 값 까지의 최대값 + 현재 값을 더했을 경우 또는 현재 값만 있을 때를 비교해서 더 큰 값을 가질 수 있다. 

 

따라서 answer 는 dp[1] ~ dp[n] 중에 최대가 되는 값을 뽑아내면 된다. 

+ 펄스 수열이 두가지가 있기에 두번 수행하면된다. 

 

 

*주의

answer 가 long 으로 선언되어 있기 때문에 long 으로 계산해야 후에 오류가 나지 않는다. 

---

전체 코드

class Solution {
    public long solution(int[] sequence) {
        long answer;
        
        int size = sequence.length;
        int[] a = new int[size];
        int[] b = new int[size];
        int n = 1;
        
        for(int i = 0; i<size; i++) {
            a[i] = sequence[i]*n;
            n *= -1;
            b[i] = sequence[i]*n;
        }
        
        // dp[n] = n 번째 원소를 포함했을 때의 최대값
        // dp[n] = MAX (dp[n-1] + a[n], a[n])
        long[] dpA = new long[size];
        long[] dpB = new long[size];
        
        dpA[0] = a[0];
        dpB[0] = b[0];
        answer = Math.max(dpA[0], dpB[0]);
    
        for(int i = 1; i<size; i++) {
            dpA[i] = Math.max(dpA[i-1] + a[i], a[i]);
            dpB[i] = Math.max(dpB[i-1] + b[i], b[i]);
    
            long max = Math.max(dpA[i], dpB[i]);
            answer = Math.max(answer, max);
        }
        
        
        return answer;
    }
}