[알고리즘] 5. 카데인(Kadane) 알고리즘 : 최대부분합 구하기

[ 1, -3, -1, 2] 와 같은 수의 나열 "수열"이 있다고 가정했을때

각 수들을 더했을때 가장 큰 수가 나오는 연속된 부분을 찾는 알고리즘을 카데인 알고리즘이라고 한다.

 

수열 알고리즘의 기초에 해당하는 문제로,

오래전 중등부 경시대회 문제로도 많이 출제되었다고 한다.

 

풀이의 핵심은,

 

1. 요소를 하나씩 더하기

2. 더한 값을 변수에 저장

3. 더한 값이 그 마지막 저장해놓은 변수값보다 크면 변수를 대입

 

이다.

 

자바 코드로 보자면,

int[] nums = {1,-3, -1, 2};

public static int maxSubArray(int[] nums) {

      //배열길이가 1일떄는 더할것이 없으므로 0번지 그대로 반환
      if(nums.length == 1) {
          return nums[0];
      }
      
      //해당 os의 int 범위에서의 최소값을 초기값으로 설정, 각 배열 요소의 합산 값 
      int maxValInt = Integer.MIN_VALUE, sumVal = 0;
        
      //1. 배열 요소를 하나씩 회전하면서 값을 더해본다 (최대 부분합을 구하기 위해서)
      for(int i = 0, j = nums.length; i < j; i++) {
          
          //2. 합산 값 대입
          sumVal += nums[i];
            
          //3. 이전 합산 저장 값과 비교하여 더 큰 값이면 치환
          if (maxValInt < sumVal) maxValInt = sumVal;
          if (sumVal < 0) sumVal = 0;
      }

      return maxValInt;
 }

와 같다.

 

반복문에서 합산값이 0보다 작게 된 경우 0으로 값을 반환할지 여부는 알고리즘 문제 출제에 따라 다르다.

 

*. 이번 알고리즘은 방송이 없습니다...