챌린지 » 최대 부분 수열의 합
최대 부분 수열의 합
문제
주어진 정수 배열에서 비연속적인 부분 수열을 선택하여 그 합이 최대가 되는 경우를 찾는 문제입니다. 선택된 수열의 인덱스는 서로 달라야 하며, 음수를 포함할 수 있습니다.
입력 형식
- 첫 번째 줄에 정수 N (1 <= N <= 1000)이 주어집니다.
- 두 번째 줄에는 N개의 정수가 주어집니다. (−10^9 <= arr[i] <= 10^9)
- 최대 부분 수열의 합을 출력합니다.
출력 형식
제약조건
1 <= N <= 1000 −10^9 <= arr[i] <= 10^9
예제
예제 1
입력
5 3 -2 5 -1 4
출력
12
설명
3, 5, 4를 선택하여 합이 12가 됩니다.
예제 2
입력
4 -1 -2 -3 -4
출력
-1
설명
모든 수가 음수일 경우 가장 큰 음수를 선택합니다.
힌트 보기
DP 배열을 사용하여 최적의 해를 저장하세요.
코드 작성
제출하려면 로그인이 필요합니다.