연속 부분 최대합 L

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 위 문제는 완전탐색, 분할 정복법 등으로 해결할 수 있지만, 문제의 크기가 1,000,000 이므로 조금 더 효율적인 알고리즘을 설계해야 함
• 따라서 각 원소를 포함하는(오른쪽 끝으로 생각) 연속 부분 중 최대값을 저장해 나가면서 마지막 원소까지 이를 결정하고,
• 해당 값들이 저장되어있는 배열의 최대값을 찾음으로써 문제를 해결할 수 있음
• 여기서 주의해야할 점은, 가장 끝에 있는 원소가 최대값이라고 생각하기 쉬운데, 이는 뒤에 있는 원소가 음수가 나올 경우 더 작아질 수 있는 상황이 발생할 수 있으므로, 각 원소를 끝으로하는 연속 부분 중 최대값을 각각 구해놓고 그 중에 최대값을 선택해야 수열의 연속 부분 최대합을 구할 수 있음
• 따라서, T[i] = i를 포함하는(오른쪽 끝으로 생각하는) 연속 부분 중 최대값이며,
• T[i] = T[i] < T[i - 1] + T[i] ? T[i - 1] + T[i] : T[i] 과 같은 점화식을 세울 수 있고, 최종적으로 Max(T[0] ~ T[n - 1])을 구해야 하므로, O(n)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

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

//MARK: - Framework
import Foundation

//MARK: - Function
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 table: [Int] = Array(repeating: 0, count: n)
    var result: Int = 0
    
    //MARK: - Process
    table[0] = array[0]
    result = table[0]
    
    for i in 1..<n {
        table[i] = array[i] < table[i - 1] + array[i] ? table[i - 1] + array[i] : array[i]
    }
    
    for number in table {
        result = result < number ? number : result
    }
    
    //MARK: - Output
    print(result)
}
solution()

 

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