1912:연속합

https://www.acmicpc.net/problem/1912

풀이

1. d[n]
   a[n]을 마지막으로 하는 연속하는 수들의 합 중 가장 큰 수

2. 예를들어,
   10 -4 3 1 5 6 -35 12 21 -1

3. d[4]

   • 5
   • 5 + 1
   • 5 + 1 + 3
   • 5 + 1 + 3 -1
   • 5 + 1 + 3 -1 -4
   • 5 + 1 + 3 -1 -4 + 10
   • 중 가장 큰 값

4. 여기서 dp 문제라고 파악해야함

5. 왜냐하면,

6. d[3] 은

   • 1
   • 1 + 3
   • 1 + 3 - 4
   • 1 + 3 - 4 + 10
   • 이기 때문이다.
   • d[3]이 d[4] 구할때 쓰임

7. 따라서
   d[4] = max ( a[4] , a[4]+d[3] )

8. 즉,
   d[n] = max ( a[n], a[n]+d[n-1] )