질문
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 문 시간 초과로 검색이 수행됩니다.
- 인덱스 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()!
)