[JS] 연속 펄스 부분 수열의 합

문제 자체는 부분수열의 합을 구하는 방법을 알면 해결할 수 있는 문제이다.

 

 

1 , -1 , 1 , -1 ...

-1 , 1 , - 1 , 1 ...

 

해당되는 펄스를 각각 곱한 2개의 수열을 만들어주면 된다.

 

이어서 dp를 활용해서 부분수열의 합중 가장 큰 값을 가지면 된다.

 

 

아래 예시를 보며 생각해보자.

2 3 -6 1 3 -1 2 4

 

dp[n] 을 n번째에 올 수 있는 가장 최대치의 부분수열의 합이라 생각하고

maxDp[n]을 n번를 무조건 포함한 가장 최대치의 부분수열의 합이라 생각하자.

 

결국 dp[n] = Math.max(dp[n-1] , maxDp[n])

 

이 되게된다.

n번째 값이 들어왔을때 이를 포함한 부분수열의 합이 더큰가 아닌가만 확인하면 되는 문제로 바뀐 것이다.

 

 

maxDp[n]은 아래와 같이 구할 수 있다.

maxDp[n] = MAt.max(maxDp[n-1] + ary[n] , ary[n])

 

즉, n-1번째 까지 부분수열의 합에 ary[n] 값을 더하거나 , 아예 ary[n] 이 더큰경우를 판별하면 된다.

 

위 점화식이 가능한 이유를 살펴보자.

 

1. 양수가 들어오는 경우 => 양수이므로 무조건 maxDp[n-1]에 n번째 수를 넣는것이 가장 클 것이다.

2. 음수가 들어오는 경우 => 음수이므로 무조건 maxDp[n-1]에 n번째 수를 넣는것이 n번째 수를 넣어야하는 입장에서는 가장 클 것이다.

3. maxDp[n-1]이 음수인 경우 => 아예 부분수열을 끊고 n번째 값 한개만 있는 부분수열이 가장 클 것이다.

 

이를 코드로 구현하면 아래와 같다.

 

function solution(sequence) {
    const ary1 = sequence.map((v,idx) => idx%2 ? v : -v)
    const ary2 = sequence.map((v,idx) => idx%2 ? -v : v)
    
    const dp1 = new Array(sequence.length)
    const maxDp1 = new Array(sequence.length)
    const dp2 = new Array(sequence.length)
    const maxDp2 = new Array(sequence.length)
    
    dp1[0] = ary1[0]
    dp2[0] = ary2[0]
    maxDp1[0] = ary1[0]
    maxDp2[0] = ary2[0]
    
    for (let i = 1 ; i < sequence.length ; i++){
        
        maxDp1[i] = Math.max(maxDp1[i-1] + ary1[i] , ary1[i])
        maxDp2[i] = Math.max(maxDp2[i-1] + ary2[i] , ary2[i])
        
        dp1[i] = Math.max(maxDp1[i] , dp1[i-1])
        dp2[i] = Math.max(maxDp2[i] , dp2[i-1])
    }
    
    return Math.max(dp1[dp1.length-1] , dp2[dp2.length-1])
}