[백준] (Swift) 1912번 - 연속합 (dp max 값 구하기!)

문제 링크

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

문제 풀이 idea

앞에서 풀던 dp 문제와 다를 것 없는 문제! 앞에서부터 더해주고 max값으로 바꿔주면 돼. 왜냐면!! 어차피 가장 큰 값을 찾는거라 계쏙 max 값으로 업데이트 되기 때문이다.

 

소스코드

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

dp[0] = arr[0]

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