🧮

Maximum Subarray

어려움 알고리즘 +40pts

Problem

Find the contiguous subarray with the largest sum.

Examples

Input: maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])

Output: 6

💡 [4, -1, 2, 1]

Explanation

이 문제는 **카데인 알고리즘(Kadane's Algorithm)**으로 최대 부분 배열 합을 구하는 방법을 학습합니다. ## 핵심 개념: 카데인 알고리즘 현재 위치까지의 최대 합을 추적하며 배열을 순회합니다. ### 핵심 아이디어 각 위치에서 선택: 1. 현재 요소부터 새로 시작 2. 이전 합에 현재 요소 추가 ### 코드 분석 ```javascript let maxSum = arr[0]; let currentSum = arr[0]; for (let i = 1; i < arr.length; i++) { currentSu...

View detailed explanation →

Key Concepts

카데인 알고리즘 동적 프로그래밍 최대 부분 합 최적화

Time: O(n) Space: O(1)

solution.js

Ctrl + Enter

Run tests to see results here.