[Algorithm] maximum-sunarray (카데인 알고리즘)

문제

# Given an integer array nums, find the subarray with the largest sum,
  and return its sum.


Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.


Constraints:
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
 

해결 방법

1. Brute force

• 시간 복잡도 : O(N²)
• 배열의 모든 값들을 더해보고 그 중 가장 큰 것 반환

public int maxSubArray(int[] nums) {

	int maxSum = Integer.MIN_VALUE;

    for (int i = 0; i < nums.length; i++) {
         int curSum = 0;
         for (int j = i; j < nums.length; j++) {
             curSum += nums[j];
             maxSum = Math.max(curSum, maxSum);
         }
     }
     return maxSum;
}

2. Kadane's Algorithm

• Dynamic Programming

  • 문제를 여러 개의 하위 문제로 나누어 푼 다음 그것을 결합하여 최종 목적에 도달하는 것
  • 한번 푼 문제는 어딘가에 저장해두고 반복하여 풀지 않음

• 카데인 알고리즘

  • 연속 부분 배열의 최대 합을 구하는 효율적인 방법

  • 시간 복잡도 O(N)

  • DP 접근법 사용

  • 원리
    - 카데인 알고리즘은 현재까지의 최대 부분 배열의 합을 유지하면서, 각 요소를 순차적으로 탐색합니다.
    - 알고리즘은 두 가지 값을 유지합니다.

    현재까지의 최대 합 (max_so_far) : 지금까지 발견한 최대 부분 배열의 합
    현재 위치에서 끝나는 최대 합 (max_ending_here) : 현재 위치에서 끝나는 부분 배열 중 최대 합

    public int maxSubArray(int[] nums) {
        int curSum = nums[0];
        int maxSum = nums[0];
    
        for (int i = 1; i < nums.length; i++) {
            curSum = Math.max(nums[i], curSum + nums[i]);  // 현재 요소를 포함한 최대 합
            maxSum = Math.max(maxSum, curSum);  // 현재까지의 최대 합으로 갱신
        }
    
        return maxSum;
    }
    

3. 정리

• 분할 정복도 고려 가능

방법	시간 복잡도	공간 복잡도
Brute Force	O(n²)	O(1)
Kadane (최적)	O(n)	O(1)
Divide & Conquer	O(n log n)	O(log n)

reference

https://medium.com/@vdongbin/kadanes-algorithm-%EC%B9%B4%EB%8D%B0%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-acbc8c279f29
https://fubabaz.tistory.com/65 - 카데인 알고리즘