[프로그래머스,Java] Level3: 연속 펄스 부분 수열의 합

 

문제분석

 

수열이 주어지고,  이 수열에다  -1 , 1 이 반복한 수열을 곱하거나  1, -1을 반복한 수열을 곱한다.

 

그렇게 나온 수열중에 부분수열이 젤 높은값을 반환하는 문제다.

 

 

DP , 부분합의 개념이없으면 풀기 힘든문제다.

 

윗개념을 사용하지않고 푼다면, 모든 부분수열을 구해야하는데, 비효율적이다.

 

 

 

첫 시작을 -1로 곱한것과 , 그대로 시작하는 결과는 매우 달라져서
둘의 경우를 분리하여 보셔야합니다.

dp를 2개를 생성해야 한다는 말이죠.

 

dp 작성
dp 기준을 잡는게 제일 중요한데, dp[n] = n까지 탐색한 모든 부분수열중 최댓값으로 잡습니다.

 

예시
{2,3,-6,1}

dp[0] 를 음수로 시작을 해보자면, dp[0] = -2 입니다.
dp[1]은 여기서 2가지 선택지가 있습니다. 0번째 숫자를 그대로 가져올지, 또는 지금부터 다시 시작할지,
우린 이 2가지 선택지를 모두 판별해야 하기때문에 다음과 같은 수식이 나옵니다.

 

dp[1] = Max(dp[0]+두번째숫자, 두번째숫자)

그리고 dp[2] 같은경우는 음수로 시작했으니,

dp[2] = Max(dp[1]+세번째숫자 * -1, 세번째숫자 * -1)이 성립합니다.

즉, 점화식은 dp[n] = Max(dp[n-1]+n번째숫자(n값의 따른 음수 또는 양수), n번째숫자(n값의 따른 음수 또는 양수))

이게 성립이됩니다.

 

서두에서 말씀햇듯이, 음수로 시작과 양수로 시작한것이 다르므로,

 

두 dp중 최대값이나오는 값을 반환 하시면 정답이 나옵니다.

문제풀이

import java.util.*;
class Solution {
    public long solution(int[] sequence) {
        long answer = 0;
        
        // 첫번째 분기 시작을 1로할까 -1로할까.. ->2개로분리
        // dp[n] = n까지 돌았는데 가장 큰 값을 추출
        // dp[n+1] = Math.max(dp[n]+현재값, 현재값)
        // dp[n]+현재값이 더 크면 수열을 1 늘리는것과 같음
        // dp[n]+현재값이 더 작으면, 수열의 스타팅포인트를 초기화 하는게 더이득임.
        
        long[] dp1 = new long[sequence.length];
        long[] dp2 = new long[sequence.length];
        
        dp1[0]=sequence[0];
        dp2[0]=sequence[0]*-1;
        
        for(int i=1;i<sequence.length;i++){
            long num= sequence[i];
            
            if(i%2==1){
                dp1[i]=Math.max(dp1[i-1]+num*-1,num*-1);
                dp2[i]=Math.max(dp2[i-1]+num,num);
            }else{
                dp1[i]=Math.max(dp1[i-1]+num,num);
                dp2[i]=Math.max(dp2[i-1]+num*-1,num*-1);
            }
        }
        
        int size =sequence.length-1;
        
        Arrays.sort(dp1);
        Arrays.sort(dp2);
        
        answer=Math.max(dp1[size],dp2[size]);
        
        return answer;
    }
}