[BOJ1912] 연속합

연속된 수의 합 중 제일 큰 합

• n개의 정수
• 수는 한 개 이상 선택
• ex) 수열 (10, -4, 3, 1, 5, 6, -35, 12, 21, -1) 정답 : 12+21 = 33

입력

• n (1<= n <= 100,000)
• n개의 정수로 된 수열 (-1,000 <= <= 1,000)

출력

• 연속된 수열의 합 중 제일 큰 합

설계

• 직전 위치의 최대값과 현재 위치의 값을 더한 것과 현재 위치의 값의 최대 비교
• dp[i] = max(dp[i-1] + ary[i], ary[i])
• dp의 각 인덱스는 계속해서 새로 갱신될 수 있으므로, 최대값을 저장할 변수를 두고, 각 dp인덱스와 비교하여 최대값 갱신

How I solved(click to github)

---

ref :
BOJ1912