[백준] 10211번: Maximum Subarray - Kotlin[코틀린]

문제

 

10211번: Maximum Subarray

 

---

풀이

 

 연속된 부분 수열의 합 중 최댓값을 구하는 전형적인 DP(Dynamic Programming) 문제이다. 입력받은 현재 값을 더해가며 최대 부분합을 갱신한다. 이때, 합이 음수라면 새로운 구간을 시작하면 된다. 

 

---

코드

 

fun main() {
    val sb = StringBuilder()
    repeat(readln().toInt()) {
        val num = readln().toInt()
        val arr = readln().split(' ').map { it.toInt() }
        val dp = IntArray(num)
        var max = arr[0]
        dp[0] = arr[0]
        
        for(i in 1 until num) {
            if(dp[i-1] < 0) dp[i - 1] = 0
            dp[i] = dp[i - 1] + arr[i]
            max = maxOf(max, dp[i])
        }

        sb.append("$max\n")
    }

    print(sb.toString())
}