[Swift] BOJ 1912 연속합

BOJ 1912 연속합

 

접근 방식

 

연속 부분합의 최댓값을 구하는 문제. dp[i]에 list[i]로 끝나는 최선의 연속합을 저장함.

 

i번째에서 dp[i-1]과 list[i-1] 중 더 큰 값을 value로 고름.

 

현재 값 list[i]가 value보다 크면 현재 값 자체가 그 자리의 최선 연속합이 됨. 다만 현재 값이 더 크더라도 value가 양수라면 value를 더하는 편이 무조건 낫기 때문에, value가 양수인지 먼저 확인함.

 

이것이 가능한 이유는 앞에서부터 계속 최선값을 골라 와서 이전 dp값이 항상 최선이라는 보장이 있기 때문임.

 

시행착오

 

알고리즘 자체는 맞았으나 예외 케이스를 놓쳐서 틀렸음. 아래 반례로 확인함. 두 번째 반례는 앞 값이 음수라 누적값이 음수가 되므로, 마지막 값 5 하나로 새로 시작해야 하는 경우임.

 

[반례]

 

10
15 40 80 84 -22 -28 72 80 69 -44
answer : 390

3
-1 -4 5
answer : 5

 

코드

 

        let input: Int = Int(readLine()!)!
        let list: [Int] = readLine()!.components(separatedBy: " ").map { Int($0)! }
        var dp = [Int](repeating: 0, count: input)
        
        dp[0] = list[0]
        
        if input >= 2 {
            dp[1] = max(dp[0]+list[1], list[1])
            
            for i in 2..<input {
                let value = max(dp[i-1],list[i-1])
                
                if value > list[i] || value > 0 {
                    dp[i] = list[i] + value
                } else {
                    dp[i] = list[i]
                }
            }
        }
        
        print(dp.max()!)