[C++] 백준 1912번 풀이 (연속합)

- 문제 (1912번) : 연속합

• 링크 : https://www.acmicpc.net/problem/1912

• 주어진 수열에서 연속된 수의 합이 가장 큰 합을 구하기.
• LIS(longist increasing subsequence) 문제 참고해 해결할 수 있음.

---

- 입력 및 출력

[입력]

• 첫째줄에 입력받을 수열의 길이 N 입력 ( 1 ≤ N ≤ 100,000 )
• 둘째줄에 N개의 정수로 이루어진 수열 입력 ( -1,000 ≤ 입력수 ≤ 1,000 )
• 입력값은 모두 정수임.

[출력]

• 첫째줄에 주어진 수열에서 연속된 수의 합이 가장 큰 합 출력.

---

- 문제풀이

• 수열의 앞부터 차례로 탐색하면서 max값 update <- DP 활용해 문제 해결
• [이전단계까지의 최댓값 + 현재값] 과 [현재값] 을 비교해

1. [이전단계까지의 최댓값 + 현재값] 이 크다면 이번단계의 최댓값도 이전단계의 최댓값과 동일
2. [현재값] 이 크다면 이번단계의 값부터 다시 연속된 값 선택

   N번째단계까지의 최댓값 : sum_max[N]
   수열에서 N번째의 값 : arr[N]
   두개의 int 중 큰 값 반환 함수 : Max (int A, int B)

   sum_max[N] = Max( (sum_max[N-1] + arr[N]), (arr[N]) )

   으로 update 할 수 있다. ( memoization )

---

- 최종코드