연속 부분 최대합

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 위 문제를 완전탐색으로 해결하게 될경우 O(n^2)으로 구간을 탐색해야 하고 구간마다 최대합을 구해야하므로, 총 O(n^3)의 시간복잡도를 가질 것임
• 위 완전탐색을 개선할 수 있는 부분은 최대합을 구하는 부분을 합을 미리 저장해놓음으로써 O(1)로 줄여 총 O(n^2)으로 시간복잡도를 줄일 수 있지만, 해당 문제의 크기는 100,000이므로 해당 시간복잡도도 효율적인 알고리즘이 아님
• 따라서 다른 알고리즘을 통해 시간복잡도를 개선할 수 있는데, 위 문제도 자기 자신 속에 최대합을 통해 문제를 해결해야 하므로 재귀호출을 이용할 수 있음
• 즉, 분할 정복법을 통해 문제를 해결할 수 있으며, 왼쪽 구간의 최대합, 오른쪽 구간의 최대합을 구하고, 경계를 포함한 왼쪽 구간의 최대합, 경계를 포함한 오른쪽 구간의 최대합을 구해 이 둘을 더함으로써 경계를 포함한 최대합을 구할 수 있고, 위 셋의 값을 비교하여 최대값을 반환함으로써 문제를 해결할 수 있음
• 분할 정복법을 통해 경계를 포함한 최대합을 구하는 시간복잡도까지 포함하여 총 O(n log n)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 연속 부분 최대합

//MARK: - Framework
import Foundation

//MARK: - Function
func getSubMax(_ array: [Int], _ start: Int, _ end: Int) -> Int {
    //array의 start 부터 end 까지의 연속 부분 최대합을 반환하는 함수
    if start >= end {
        return array[start]
    }
    
    let mid: Int = (start + end) / 2
    let leftSubMax: Int = getSubMax(array, start, mid)
    let rightSubMax: Int = getSubMax(array, mid + 1, end)
    
    var leftSum, leftMax, rightSum, rightMax, middleSubMax: Int
    leftSum = 0
    leftMax = -987987987
    rightSum = 0
    rightMax = -987987987
    
    for i in stride(from: mid, through: start, by: -1) {
        leftSum += array[i]
        
        leftMax = leftMax < leftSum ? leftSum : leftMax
    }
    
    for i in mid + 1...end {
        rightSum += array[i]
        
        rightMax = rightMax < rightSum ? rightSum : rightMax
    }

    middleSubMax = leftMax + rightMax
    
    if leftSubMax > rightSubMax && leftSubMax > middleSubMax {
        return leftSubMax
    } else if rightSubMax > leftSubMax && rightSubMax > middleSubMax {
        return rightSubMax
    } else {
        return middleSubMax
    }
}

func solution() -> Void {
    //MARK: - Input
    guard let n: Int = Int(readLine() ?? "0") else { return }
    guard let inputArray: [String] = readLine()?.components(separatedBy: " ") else { return }
    let array: [Int] = inputArray.map { Int($0) ?? 0 }
    var result: Int = 0
    
    //MARK: - Process
    result = getSubMax(array, 0, n - 1)
    
    //MARK: - Output
    print(result)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.