10211번: Maximum Subarray

방법 1

문제풀이 아이디어

정의: f(i, j) = X[i] + ... + X[j]
초기값: f(i, i) = X[i]
점화식: f(i, j) = f(i, j - 1) + X[j]

위 DP를 활용해서 모든 부분 수열의 합을 종류별로 구한 다음에 완전 탐색으로 최댓값을 구한다.

코드

let T = Int(readLine()!)!

for _ in 0..<T {
    let N = Int(readLine()!)!
    let X = readLine()!.split(separator: " ").map { Int(String($0))! }
    var cache = Array(repeating: Array(repeating: 0, count: N), count: N)
    
    // 모든 부분 수열의 합 구하기
    for i in 0..<N {
        for j in 0..<N {
            if i > j {
                continue
            } else if i == j {
                cache[i][j] = X[i]
            } else {
                cache[i][j] = cache[i][j - 1] + X[j]
            }
        }
    }
    
    // 완전탐색을 통해서 최댓값 구하기
    var result = Int.min //👉 최댓값을 구할 때는 Int의 가장 작은 값과 비교
    for i in 0..<N {
        for j in 0..<N {
            if i > j { continue }
            result = max(cache[i][j], result)
        }
    }
    print(result)
}

방법 1의 단점

O(N^2)의 시간복잡도를 가진다.

방법 2: 시간 복잡도 O(N)으로 개선

문제 풀이 아이디어

정의: f(i) = (i를 포함한 최대 부분배열의 합)
초깃값: f(0) = X[0]
점화식: f(i) = max(f(i - 1) + X[i], X[i])
	👉 지금까지의 합에 이어가는 것이 좋으냐 처음부터 시작하는 것이 좋은가?

이렇게 구하고 나서 DP를 완전탐색하면서 최댓값을 구한다.

코드

let T = Int(readLine()!)!

for _ in 0..<T {
    let N = Int(readLine()!)!
    let X = readLine()!.split(separator: " ").map { Int(String($0))! }
    var cache = [X[0]]
    for i in 1..<N {
        cache.append(max(cache[i - 1] + X[i], X[i]))
    }
    
    var result = Int.min
    for i in 0..<N {
        result = max(cache[i], result)
    }
    print(result)
}