백준 - 연속합 2 (13398)

let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
var left = Array(repeating: 0, count: n)
var right = Array(repeating: 0, count: n)
var answer = arr[0]

left[0] = arr[0]
right[n - 1] = arr[n - 1]

for i in 1..<n {
    left[i] = max(arr[i], left[i - 1] + arr[i])
    answer = max(answer, left[i])
}

for i in (0..<n - 1).reversed() {
    right[i] = max(arr[i], right[i + 1] + arr[i])
}

// i번째 인덱스 뺐을 때 최댓값 찾기
for i in stride(from: 1, to: n - 1, by: 1) {
    answer = max(answer, left[i - 1] + right[i + 1])
}

print(answer)

left에는 0~i번째까지 길이에서 i를 포함해서 연속으로 수를 선택하여 구할 수 있는 최대 합을 저장한다.

right은 반대로 오른쪽에서부터 시작해서 i번째 값을 포함한 최대 연속 합을 저장하는데, 이건 i번째 인덱스를 뺐을 때 최대 연속 합을 구하기 위해 사용된다.