1/29
Loading...
🎯연속 부분 배열의 최대 합
배열에서 연속된 부분의 합이 최대가 되는 구간을 찾습니다! • 배열: [-2, 1, -3, 4, -1, 2, 1, -5, 4] 예: [4, -1, 2, 1]의 합 = 6 이 배열에서 합이 가장 큰 연속 구간은? 핵심: 음수가 있어도 연속해서 더하면 더 큰 합이 될 수 있음!
Loading...
배열에서 연속된 부분의 합이 최대가 되는 구간을 찾습니다! • 배열: [-2, 1, -3, 4, -1, 2, 1, -5, 4] 예: [4, -1, 2, 1]의 합 = 6 이 배열에서 합이 가장 큰 연속 구간은? 핵심: 음수가 있어도 연속해서 더하면 더 큰 합이 될 수 있음!
Kadane's Algorithm은 배열에서 연속된 부분 배열의 합이 최대가 되는 구간을 O(n) 시간에 찾는 알고리즘입니다. 각 위치에서 '이어갈지, 새로 시작할지'만 결정하면 됩니다.