← 8주차 · 투 포인터와 슬라이딩 윈도우
보통DP배열

가장 큰 연속 부분 수열의 합

정수 배열 nums가 주어져요. 길이가 1 이상인 연속한 부분 수열 중 원소의 합이 가장 큰 값을 반환해요.

배열의 모든 원소가 음수일 수도 있어요. 이때는 가장 큰(0에 가까운) 원소 하나가 답이 돼요.

예시

예시 1
입력
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
출력
6
설명
부분 수열 [4, -1, 2, 1]의 합이 6으로 가장 커요.
예시 2
입력
nums = [1]
출력
1
예시 3
입력
nums = [5, 4, -1, 7, 8]
출력
23

제한 사항

  • 1 ≤ nums.length ≤ 100,000
  • -10,000 ≤ nums[i] ≤ 10,000
각 위치에서 '여기서 끝나는 최대 합'은 max(현재 값, 이전까지의 최대 합 + 현재 값) 이에요. 이 값을 훑으면서 전체 최댓값을 갱신해요 (카데인 알고리즘).
javascript
function maxSubArray(nums) {
  let best = nums[0];
  let cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }
  return best;
}
이전 문제정렬된 배열 중복 제거
다음 문제중복 없는 가장 긴 부분 문자열
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.