백준 11055번 가장 큰 증가하는 부분 수열 Kotlin

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

문제

---

생각하기

---

동작

결과

코드

---

import java.io.BufferedWriter
import java.io.File
import java.io.OutputStreamWriter
import java.util.*

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private lateinit var arr: IntArray
private lateinit var memo: IntArray

fun main() {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()
    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    var max = 0
    for (i in 0 until N) {
        max = Math.max(max, LIS(i))
    }

    sb.append(max)
    return sb.toString()
} // End of solve()

private fun LIS(n: Int): Int {
    if (memo[n] != -1) return memo[n]

    var max = arr[n]
    for (i in n + 1 until N) {
        if (arr[n] < arr[i]) {
            max = Math.max(max, LIS(i) + arr[n])
        }
    }

    memo[n] = max
    return memo[n]
} // End of LIS()

private fun input() {
    N = br.readLine().toInt()
    StringTokenizer(br.readLine()).run {
        arr = IntArray(N) {
            nextToken().toInt()
        }
    }
    memo = IntArray(N) { -1 }
} // End of input()