BOJ-1912 연속합 Swift

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

내가 푼 풀이

• 연속된 몇개의 수의 합들의 최댓값을 구하면 된다.
• 이중 for문을 통한 완전 탐색은 시간초과가 뜬다.
• index 0 의 최대로 더할수 있는 갯수는 정수 n만큼, 마지막 원소의 최대로 더할수 있는 갯수는 마지막원소 하나 뿐이다.

 

n개의 정수로 이루어진 수열의 배열 arr

연속된 수의 합의 최댓값 점화식: dp[i] = max(dp[i-1] + arr[i], arr[i])

max(dp[i-1] + arr[i], arr[i]) 에서 arr[i] 가 더 큰경우, i-1까지 더한 값들을 모두 지우고 i번째에서 새출발 하는 것이다.

이는, 연속적으로 수열의 합을 구해도 i-1번째까지의 합이 더 작으므로, 더해봤자 최댓값을 구할 수 없게되는 것이다.

 

 

import Foundation

var count = Int(String(readLine()!))!
var dp = Array(repeating: 0, count: count)
var arr = readLine()!.split(separator: " ").map{ Int(String($0))!}

for i in 0..<count {
    if i == 0 {
        dp[i] = arr[0]
        continue
    }
    dp[i] = max(arr[i], dp[i-1] + arr[i])
}
print(dp.max()!)