본문 바로가기

알고리즘

연속 수열의 최대합

Basic 100 · 24번Lv. 2동적 계획법

연속 수열의 최대합

문제 설명

정수로 이루어진 배열이 주어집니다. 이 배열에서 연속된 부분 수열의 합 중 최댓값을 반환하는 코드를 작성해주세요.


제한 사항

  • 배열의 길이는 최소 1에서 최대 100까지입니다.
  • 배열의 각 요소는 -100 이상 100 이하의 정수입니다.
  • 연속된다는 것은 배열 안에서 인덱스가 이어진다는 뜻입니다.
  • 부분 수열에는 원소가 1개 이상 있어야 합니다. 모든 수가 음수이면 그중 가장 큰 수가 답입니다.

입출력 예

입력 (배열)반환값 (최대 부분 수열 합)
[1, -2, 3, 4, -1, 2, 1, -5, 4]9
[-2, -3, 4, -1, -2, 1, 5, -3]7

입출력 설명

첫 번째 예시에서 가장 큰 부분 수열 합은 [3, 4, -1, 2, 1]으로, 합계는 9입니다. 두 번째 예시에서는 [4, -1, -2, 1, 5]의 부분 수열 합이 최대이며, 합계는 7입니다.

예시 테스트

#입력기대값
1[1, -2, 3, 4, -1, 2, 1, -5, 4]9
2[-2, -3, 4, -1, -2, 1, 5, -3]7
3[-1, -2, -3, -4]-1

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.