Baekjoon(Kotlin) - 11054. 가장 긴 바이토닉 부분 수열

URL : https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

 

[ RESULT ]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.max

val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))

fun main() {

    val N = br.readLine().toInt()
    val A = br.readLine().split(" ").map { it.toInt() }
    val reverse_A = A.reversed()

    val visit: MutableList<Int> = MutableList(N) { 1 }
    val rev_visit: MutableList<Int> = MutableList(N) { 1 }

    val result: MutableList<Int> = MutableList(N) { 0 }

    for(i in 0 until N) {
        for(j in 0 until i) {
            if(A[i] > A[j]) { visit[i] = max(visit[i], visit[j]+1) }
            if(reverse_A[i] > reverse_A[j]) { rev_visit[i] = max(rev_visit[i], rev_visit[j]+1) }
        }
    }

    for(x in 0 until N) { result[x] = visit[x] + rev_visit[N - x - 1] - 1 }

    bw.write(result.max().toString())


    br.close()
    bw.close()
}

 

증가하는 수열의 길이 + 감소하는 수열의 길이의 합이 가장 큰 바이토닉 수을 찾으면 된다.