✓

태그:

14. 동적 계획법 1

길이가 N인 수열의 연속합의 최대값을 구하는 문제입니다. 먼저 길이가 N인 DP 배열을 만듭니다. 각 원소는 지금까지의 부분 수열에서 얻을 수 있는 연속합의 최대값을 의미합니다. 먼저 첫 번째 원소에는 원래 수열의 첫 번째 원소를 대입하고, 그 뒤로는 이전까지의 연속합이 양수이면 여기에 수열의 i번째 원소를 더한 값을, 그렇지 않다면 그냥 자기 자신을 저장하는 방식으로 DP 배열을 채웁니다. 이 DP 배열의 최대값을 구하여 출력하면 됩니다.

소스 코드

언어	코드	시간
Python 3	코드(Github) / 코드(백준)	2020-04-01 12:09:41

---