[백준] 1912번: 연속합

문제

https://www.acmicpc.net/problem/1912

풀이

• 메모이제이션
• i 번째 값을 반드시 포함하여 더한 값과 i 번째 하나의 값 중 큰 값을 계산한다.
• dp 배열 중 가장 큰 값을 출력한다.

import kotlin.math.max

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val numbers = br.readLine().toString().split(" ").map { it.toInt() }
    val dp = Array(n) { 0 }
    dp[0] = numbers[0]
    for (i in 1 until n) {
        dp[i] = max(numbers[i] + dp[i - 1], numbers[i])
    }
    bw.write("${dp.maxOf { it }}")
    bw.close()
    br.close()
}

더 좋은 풀이 있으면 댓글 달아주세요!!!