[알고리즘][KOTLIN] 구간 합

구간 합

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

 

0번째부터 i 번째까지의 합을 구하는 공식

    - S[i] = A[0] + A[1] + A[2] + … + A[i - 1] + A[i - 2]

        - 배열     A [15, 13, 10, 7, 3, 12]

        - 합 배열 S [15, 28, 38, 45, 48, 60]

 

S[i] = S[i - 1] + A[i]

 

i번째부터 j번째까지의 합을 구하는 공식(구간 합)

S[j] - S[i - 1]

 

배열이 변경될 경우 -> 세그먼트 트리를 사용한다.

 

문제

주어진 배열에서 k 개수 만큼 연속된 원소를 추출하여 새로운 배열을 만들었을 때 만들어진 새로운 배열 중 최대값을 구하여라

입력

배열 : [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]
k   : 3

출력

32

코드

fun main(args: Array<String>) {
    println(getResult(intArrayOf(10, -4, 3, 1, 5, 6, -35, 12, 21, -1), 3))
}

private fun getResult(number: IntArray, k: Int): Int {
    val s = IntArray(number.size) { 0 }
    s[0] = number[0]

    // 0부터 i 번째까지 값을 s 배열에 저장 한다.
    for (i in 1 until number.size) {
        s[i] = s[i - 1] + number[i]
    }

    // 0번째부터 2번째까지의 합    : S[2]
    // 1번째부터 3번째까지의 합    : S[3] - S[0]
    // 2번째부터 4번째까지의 합    : S[4] - S[1]
    // ...
    // n-2번째 부터 n번째까지의 합 : S[n] - S[n - 3]
    var result = s[2]

    for (i in 3 until number.size) {
        result = Math.max(result, s[i] - s[i - 3])
    }

    return result
}