배열에서 최대 부분합을 찾기 위해 Kadane's Algorithm을 적용해 O(n) 시간 복잡도와 O(1) 공간 복잡도 달성

Context

배열에서 연속된 부분의 최대 합을 구하는 문제는 모든 가능한 부분배열을 확인하는 방식으로 접근하면 불필요한 계산이 발생한다.

Technical Solution

• Kadane's Algorithm 적용: 현재 부분합과 지금까지의 최대합을 추적하는 동적 계획법 기반 접근
• 배열 순회 시 각 요소마다 결정: 현재 합에 추가할지 vs 새로운 부분배열 시작할지
• Math.max(arr[i], currentSum + arr[i])로 계산: 현재 요소 단독 vs 이전 합에 추가 중 선택
• 한 번의 배열 순회로 최종 답을 도출: 인덱스 1부터 배열 끝까지 반복
• 초기값 설정: currentSum = arr[0], maxSum = arr[0]로 시작

Impact

시간 복잡도 O(n)으로 배열을 한 번만 순회하며, 공간 복잡도 O(1)로 추가 자료구조 불필요

Key Takeaway

동적 계획법의 핵심은 현재 상태와 지금까지의 최적값 두 변수만 유지하면서 불필요한 재계산을 피하는 것이다. 이 패턴은 최대값/최소값 추적이 필요한 다양한 부분배열 관련 문제 해결에 적용할 수 있다.