1.5.5 합이 최대인 부분 배열 찾기
문제 1-5 양의 정수와 음의 정수로 된 배열이 있을 때 원소의 합이 최대인 연속된 부분 배열을 찾으세요.
해결책
1. 합이 최대인 부분 배열은 단일 스캔으로 찾을 수 있습니다. 현재까지 전역 최대 합과 현재 원소를 포함하는 최대 합을 기억해 둡니다.
2. 현재 원소를 포함하는 최대 합보다 전역 최대 합이 작다면 전역 최대 합을 현재 최대 합으로 업데이트합니다.
3. 마지막으로 전역 최대 합을 반환합니다.
해결책 1-5
int maxSubArraySum(int a[], int size)
{
int maxSoFar = 0, maxEndingHere = 0;
for (int i = 0; i < size; i++) {
maxEndingHere = maxEndingHere + a[i];
if (maxEndingHere < 0) {
maxEndingHere = 0;
}
if (maxSoFar < maxEndingHere) {
maxSoFar = maxEndingHere;
}
}
return maxSoFar;
}
분석 시간 복잡도는 O(n)입니다.