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

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

프로그래머스

 

솔직히 문제 자체가 복잡했다고 생각하진 않는다

그냥 내가 풀이법을 못떠올렸을뿐..

 

처음에는 부분 수열을 죄다 만들어서 처리해볼려고 했다.

class Solution {
    fun solution(sequence: IntArray): Long {
        var answer: Long = -99999
        var maxPulse1: Long = Long.MIN_VALUE
        var maxPulse2: Long = Long.MIN_VALUE
        val contiguousSubsequences = getAllSubsequences(sequence)
        contiguousSubsequences.forEach{
            var currentPulse1: Long = 0
            var currentPulse2: Long = 0
             for (i in it.indices) {
                 
                val pulse1 = if (i % 2 == 0) it[i] else -it[i]
                val pulse2 = if (i % 2 == 0) -it[i] else it[i]

                currentPulse1 = maxOf(currentPulse1 + pulse1, pulse1.toLong())
                currentPulse2 = maxOf(currentPulse2 + pulse2, pulse2.toLong())

                maxPulse1 = maxOf(maxPulse1, currentPulse1)
                maxPulse2 = maxOf(maxPulse2, currentPulse2)
            }
        }

        
        
        return maxOf(maxPulse1, maxPulse2)
    }

    fun getAllSubsequences(arr: IntArray): List<List<Int>> {
        val subsequences = mutableListOf<List<Int>>()
        var currentSubsequence: MutableList<Int>

        for (i in arr.indices) {
            currentSubsequence = mutableListOf()
            for (j in i until arr.size) {
                currentSubsequence.add(arr[j])
                subsequences.add(ArrayList(currentSubsequence))
            }
        }

        return subsequences
    }
    
}

 

하지만? 역시나 조건의 배열 길이가 길어서 테스트 실행은 통과했으나 좀 길어지면

메모리 초과가 발생했다.

 

고민을 더 해보다가 결국 찾아봤다. ㅠ

dp 를 이용한 풀이가 많았는데 결국 배열의 합을 구하고 순서대로 계산해나가는거라서

 

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

라는 아이디어를 index 까지의 부분 수열의 합을 갱신해나가는 것으로  풀어주면 된다.

 

아래는 참고한 블로그의 답이다.

class SumOfSequences {
    fun solution(sequence: IntArray): Long {
        var pDp = Array<Long>(sequence.size){ 0 }
        var mDp = Array<Long>(sequence.size){ 0 }
        var op = 1

        sequence.forEachIndexed { idx, value ->
            if(idx == 0){
                pDp[0] = value.toLong()
                mDp[0] = -value.toLong()
            }else{
                pDp[idx] = maxOf(pDp[idx - 1] + value * op, value.toLong() * op)
                mDp[idx] = maxOf(mDp[idx - 1] - value * op,  -value.toLong() * op)
            }

            op = -op
        }

        return maxOf(pDp.maxOrNull()!!, mDp.maxOrNull()!!)
    }
}
//출처 : https://anjji.tistory.com/66