[C++/백준] 1912번: 연속합

문제 바로가기

(하단 이미지 링크)

문제 해결 아이디어

• 점화식 도출 과정
  1. DP[A] = B 를 A번째 숫자까지의 최댓값 B라고 정의
  2. 예를 들어, 길이가 3인 [ 10, -4, 3 ] 수열이 있다고 생각해보자
  3. DP[0] = 배열 index 0번째 숫자까지의 최댓값이므로 10
  4. DP[1] = 배열 index 1번째 숫자까지의 최댓값은 0번째 숫자 + 1번째 숫자 = 10 + (-4) = 6 또는 1번째 숫자 = -4 두가지 중 최댓값 6
  
  따라서 DP[N] = max(arr[N], DP[N - 1] + arr[N]) 의 점화식 도출

코드