[백준] 10211번 Maximum Subarray(브루트포스 - 완전탐색)[Kotlin - 코틀린]

백준 1111번 문제입니다. (solved.ac) 기준 실버 5 문제입니다.

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

10211번: Maximum Subarray

문제

문제 접근

문제의 제목 그대로 부분 배열의 합이 최대가 되는 경우를 찾고 해당 부분배 열의 합을 구하는 문제입니다.

부분 배열이란 배열내의 연속된 부분들을 뜻합니다. 

배열의 크기인 n이 1000이하라서 n^2인 완전탐색을 진행해도 시간초과가 발생하지 않을 것이라고 판단했습니다.

완전탐색으로 모든 부분 배열의 합을 구해보고 더 큰값이 나올 때마다 갱신하여 최대값이 담기도록 하였습니다.

단, 배열의 원소들 중 절대값이 1000이하 이므로 최초 부분 배열의 합은 -1000001로 초기화 해주었습니다. (n의 크기가 1000이며 모든 원소가 -1000일 때 보다 1더 작게)

정답 코드

fun main() {

    val t = readln().toInt()

    repeat(t){

        val size = readln().toInt()
        // 부분수열의 합들 중 최대
        var sumOfMaximumSubarray = -1000001
        // 수열
        val array = readln().split(" ").map{ it.toInt() }

        // 부분수열들을 완전 탐색
        for(start in 0 until size){
            for(end in start until size){
                val sumOfSubarray = array.subList(start,end+1).sum()
                // 부분수열의 합들 중 최대값을 넣어줌.
                if(sumOfMaximumSubarray < sumOfSubarray) sumOfMaximumSubarray = sumOfSubarray
            }
        }
        println(sumOfMaximumSubarray)
    }
}