Kadane's Algorithm

Kadane's Algorithm은 배열에서 연속된 요소들의 부분 배열 중 가장 큰 합을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 O(n) 시간 복잡도로 동작하므로, 배열을 한 번만 순회하여 문제를 해결할 수 있습니다. 문제는 주로 "최대 부분 배열 합" (Maximum Subarray Sum) 문제라고 불립니다.

알고리즘 설명:

• 배열의 각 요소를 차례대로 살펴보며, 현재 위치까지의 최대 부분 배열 합을 계산합니다.
• 부분 배열의 합이 음수로 떨어지면 그 이전의 부분 배열은 버리고, 새로운 부분 배열을 시작합니다.
• 결국 가장 큰 부분 배열의 합을 찾아냅니다.

원리:

1. 현재까지의 최대 부분 합(max_ending_here)을 유지합니다.
2. 최대 전체 합(max_so_far)을 유지합니다.
3. 각 단계에서 현재까지의 최대 부분 합을 갱신하고, 이를 최대 전체 합과 비교하여 더 큰 값을 저장합니다.

단계:

1. 배열을 순회하면서 각 요소를 더하여 현재까지의 부분 합을 계산합니다.
2. 만약 현재 부분 합이 음수가 되면, 이전의 부분 배열을 버리고 새로운 부분 배열을 시작합니다.
3. 그 과정에서 최대 부분 합을 갱신합니다.

예시:

배열이 [-2,1,-3,4,-1,2,1,-5,4]일 때,

• 부분 배열 [4,-1,2,1]의 합은 6이므로 최대 부분 배열의 합은 6입니다.

코드 구현 (Java):

class Solution {
    public int maxSubArray(int[] nums) {
        // 배열의 첫 번째 값으로 초기화
        int maxSoFar = nums[0];  // 최대 전체 합
        int maxEndingHere = nums[0];  // 현재까지의 최대 부분 합

        // 배열을 순회하면서 최대 부분 배열 합을 구함
        for (int i = 1; i < nums.length; i++) {
            // 현재 값(nums[i])을 더한 부분 배열과, 새롭게 시작하는 부분 배열 중 더 큰 것을 선택
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            // 전체 중에서 가장 큰 부분 배열 합을 갱신
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;  // 최대 부분 배열 합 반환
    }
}

동작 과정:

1. maxEndingHere: 현재까지의 부분 배열의 최대 합을 유지합니다. 새로운 요소를 추가할 때마다 maxEndingHere를 갱신합니다.
2. maxSoFar: 전체에서 가장 큰 부분 배열 합을 유지합니다. maxEndingHere가 갱신될 때마다 maxSoFar도 갱신됩니다.

예시 실행:

int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
Solution solution = new Solution();
System.out.println(solution.maxSubArray(nums));  // 출력: 6

시간 복잡도:

• O(n): 배열을 한 번만 순회합니다.

공간 복잡도:

• O(1): 추가적인 배열을 사용하지 않고 상수 공간만 사용합니다.

요약:

Kadane's Algorithm은 연속된 부분 배열의 합을 효율적으로 계산하여, 최대 부분 배열의 합을 찾는 매우 빠른 알고리즘입니다. 시간 복잡도가 O(n)이므로 큰 배열에서도 빠르게 동작합니다.