Class‎ > ‎


모든 입력 값은 매우 큰 값입니다. 예제에서는 작은 수의 경우를 예를 들었음

Q1. 최대 합산 값을 가지는 하위 배열을 구하는 알고리즘을 제안하세요. 제안한 알고리즘의 시간 복잡도는 얼마인가요?
예) {-2, -5, 6, -2, -3, 1, 5, -6} 에서 {6, -2, -3, 1, 5} = 7. 배열의 순서는 바꿀 수 없습니다.

Divide and Conquer | Set 3 (Maximum Subarray Sum)

The naive method is to run two loops. The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum. 

Finally return the overall maximum. The time complexity of the Naive method is O(n^2).

Using Divide and Conquer approach, we can find the maximum subarray sum in O(nLogn) time. Following is the Divide and Conquer algorithm.

1) Divide the given array in two halves
2) Return the maximum of following three
….a) Maximum subarray sum in left half (Make a recursive call)
….b) Maximum subarray sum in right half (Make a recursive call)
….c) Maximum subarray sum such that the subarray crosses the midpoint

The lines 2.a and 2.b are simple recursive calls. How to find maximum subarray sum such that the subarray crosses the midpoint? We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. Finally, combine the two and return.

// A Divide and Conquer based program for maximum subarray sum problem
#include <stdio.h>
#include <limits.h>
// A utility funtion to find maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }
// A utility funtion to find maximum of three integers
int max(int a, int b, int c) { return max(max(a, b), c); }
// Find the maximum possible sum in arr[] auch that arr[m] is part of it
int maxCrossingSum(int arr[], int l, int m, int h)
    // Include elements on left of mid.
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = m; i >= l; i--)
        sum = sum + arr[i];
        if (sum > left_sum)
          left_sum = sum;
    // Include elements on right of mid
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = m+1; i <= h; i++)
        sum = sum + arr[i];
        if (sum > right_sum)
          right_sum = sum;
    // Return sum of elements on left and right of mid
    return left_sum + right_sum;
// Returns sum of maxium sum subarray in aa[l..h]
int maxSubArraySum(int arr[], int l, int h)
   // Base Case: Only one element
   if (l == h)
     return arr[l];
   // Find middle point
   int m = (l + h)/2;
   /* Return maximum of following three possible cases
      a) Maximum subarray sum in left half
      b) Maximum subarray sum in right half
      c) Maximum subarray sum such that the subarray crosses the midpoint */
   return max(maxSubArraySum(arr, l, m),
              maxSubArraySum(arr, m+1, h),
              maxCrossingSum(arr, l, m, h));
/*Driver program to test maxSubArraySum*/
int main()
   int arr[] = {2, 3, 4, 5, 7};
   int n = sizeof(arr)/sizeof(arr[0]);
   int max_sum = maxSubArraySum(arr, 0, n-1);
   printf("Maximum contiguous sum is %d\n", max_sum);
   return 0;

Time Complexity: maxSubArraySum() is a recursive method and time complexity can be expressed as following recurrence relation.
T(n) = 2T(n/2) + Θ(n)
The above recurrence is similar to Merge Sort and can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is Θ(nLogn).

The Kadane’s Algorithm for this problem takes O(n) time. Therefore the Kadane’s algorithm is better than the Divide and Conquer approach, but this problem can be considered as a good example to show power of Divide and Conquer. The above simple approach where we divide the array in two halves, reduces the time complexity from O(n^2) to O(nLogn).

Q2. 프로세스 별 필요한 수행 시간이 다를 때, 다중 CPU 코어를 사용하여 가장 짧은 시간에 전체 job을 종료시킬 수 있는 알고리즘을 제안하고 복잡도를 계산하세요. 제안한 알고리즘은 최적해를 나타내나요?
예) 6개 프로세스 별 시간과 3개의 코어 경우, p1=2, p2=2, p3 = 2, p4=3, p5=4, p6=6 => c1={p1, p2}, c2={p3, p4}, c3={p5, p6} 면 max (c1=4, c2=5, c3=10) = 10

Greedy Algorithm:
 • Order the items arbitrarily. 
 • Go down the list of items, scheduling item ti on the machine that has been used the least so far.

Proof. Definitions: 
 • Let M be the machine with the maximum load in the greedy solution. 
 • Let tj be the last job assigned to M. 
 • Let Li be the load the greedy algorithm places on machine i. (Note: G(I) = LM.)