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

사용 언어: Kotlin

 

문제

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

프로그래머스

펄스 수열이란 1 혹은 -1로 시작하여 1과 -1이 반복되는 수열이다.

수열이 주어지고 이 수열과 펄스 수열의 각 요소를 곱한 수열이 있을 때, 그 요소들 중 연속으로 요소를 뽑아 합을 가장 크게 만들 수 있는 값을 return한다.  

제한사항

sequence = 제시되는 수열

1 <= sequence의 길이 <= 500,000

-100,000 <= sequence[i] <= 100,000

풀이

펄스 수열은 -1로 시작할 수도, 1로 시작할 수도 있기 때문에, sequence에 두 펄스 수열을 곱한 배열 2개를 가지고 푸는 것으로 생각했다. 그럼 펄스 수열을 더 이상 신경쓰지 않아도 된다.

부분수열의 합을 구하며 수열을 순회했을 때, 수열의 각 요소와 이전까지의 부분수열을 합했을 때의 경우는 크게 3가지 경우로 나눌 수 있다.

1. 양수 = 수열의 합을 증가시키므로, 더해도 된다.
2. 0 = 수열의 합이 유지되므로, 더해도 되고, 더하지 않아도 된다.
3. 음수 = 이전까지의 요소로 부분수열을 종료해야 한다.

그럼 수열을 순회했을 때, 만나는 요소의 경우와 그에 따른 처리 방법은 아래와 같다.

1. 양수 = 부분수열에 포함한다.
2. 0 = 부분수열에 포함한다.
3. 음수 = 위의 경우의 수에 따라 다르게 처리한다.
   1. 부분수열과의 합 => 양수 = 이전까지의 부분수열의 합을 저장한 후, 더한다.
   2. 부분수열과의 합 => 0 = 이전까지의 부분수열의 합을 저장한 후, 더한다.
   3. 부분수열과의 합 => 음수 = 이전까지의 부분수열의 합을 저장한 후, 이후 나오는 양수부터 새로 부분수열을 시작한다.

dp[i] = i번째 원소까지의 부분수열의 합이라고 정의한다.

dp[i] = dp[i-1] + sequence[i] (dp[i-1] + sequence[i] >= 0)

dp[i] = 0 (dp[i-1] + sequence[i] < 0)

이후, 배열에 저장된 값 중 최대값을 뽑아내면 된다.

코드

fun solution(sequence: IntArray): Long {
    val mapper1 = intArrayOf(1,-1)
    val case1 = sequence.mapIndexed { index, i ->
        (i * mapper1[index%2]).toLong()
    }
    val mapper2 = intArrayOf(-1,1)
    val case2 = sequence.mapIndexed { index, i ->
        (i * mapper2[index%2]).toLong()
    }
    val dp1 = arrayListOf(max(0, case1[0]))
    for(i in 1 until case1.size) {
        dp1.add(max(max(dp1[i-1] + case1[i], case1[i]), 0))
    }
    val dp2 = arrayListOf(max(0, case2[0]))
    for(i in 1 until case2.size) {
        dp2.add(max(max(dp2[i-1] + case2[i], case2[i]), 0))
    }
    return max(dp1.maxOf { it }, dp2.maxOf { it })
}