[백준] 연속합 (1912)

문제 설명

백준 1912번 문제 링크

입력 및 출력

» 입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

» 출력

첫째 줄에 답을 출력한다.

예제 입출력(테스트케이스)

입력	출력
10 10 -4 3 1 5 6 -35 12 21 -1	33
10 2 1 -4 3 4 -4 6 5 -5 1	14
5 -1 -2 -3 -4 -5	-1

문제 풀이 (KOTLIN)

문제 참고

import kotlin.math.max

var max = 0
var dp = arrayOf<Int?>()
var arr = intArrayOf()

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()

    arr = readLine()
        .split(" ")
        .map { it.toInt() }
        .toIntArray()
    dp = Array<Int?>(N) { null }

    dp[0] = arr[0]
    max = arr[0]

    topDown(N - 1)
    println(max)
}

fun topDown(N: Int): Int {
    if (dp[N] == null) {
        dp[N] = max(topDown(N - 1) + arr[N], arr[N])
        max = max(dp[N]!!, max)
    }

    return dp[N]!!
}

문제 풀이 (SWIFT)

문제 참고

let N = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map { Int($0)! }
var dp = [Int](repeating: 0, count: N)

dp[0] = arr[0]

for i in 1..<N {
    dp[i] = max(arr[i], dp[i - 1] + arr[i])
}

print(dp.max()!)