[Algorithm] Maximum Sum Interval (Divide & Conquer)

Maximum Sum Interval을 Divide & Conquer로 풀어보겠다.

Maximum Sum Interval

N개의 정수 a1, a2, ..., an이 주어진다.

이 중 하나 혹은 그 이상의 연속된 정수들을 더하여 만들수 있는 최댓값은?

 

세가지 케이스가 있다.

Case 1) 부분 배열 A′[low..mid]에 완전히 포함되는 경우

(low≤i≤j≤mid)

 

Case 2) 부분 배열 A′[mid+1..high]에 완전히 포함되는 경우

(mid<i≤j≤high)

 

Case 3) 중간값에 걸쳐있는 경우

(low≤i≤mid<j≤high)

 

 

int max_subArray(int a[], int left, int right){ //Pesudo 코드
	
    if(right == left)
    	return 0;
    mid = (left + right) /2
  	
    sum1 = max_subArray(a, left, mid);  //왼쪽 
    sum2 = max_subArray(a, mid+1, right); //오른쪽
    
    leftSum = 0
    leftMaxVal = 0
    for(i = mid; i >= left i--){
    	leftSum += a[i]
     	if(leftSum > leftMaxVal){
        	leftMaxVal = leftSum
        }
    }
    
    rightSum = 0
    rightMaxVal = 0
    for(i = mid+1; i <=right; i++{
    	rightSum += a[i]
        if(rightSum > rightMaxVal){
        	rightMaxVal = rightSum
        }
    }
    
   midSum = leftMaxVal + rightMaxVal
   
   max = (sum1 > sum2) ? sum1: sum2
   max = (max > sum3)? max: midSum
   
   return max
    
}

 

시간 복잡도

∴T(n)=2T(n/2)+Θ(n)

 

T(n)=2T(n/2)+Θ(n) 상에서  

 

a=2,b=2  이므로 h(n)=nlog22=n 이다.

 

f(n)/h(n)=Θ(n)/n=n/n=Θ(1) 이므로

 

T(n)=Θ(h(n)logn)=Θ(nlogn)