복잡도 nlog(n)되도록 최대연속부분수열 도출하기

int cal(int * arr, int left, int right)

{

if (left == right)

return arr[left];

 

int mid = (left + right) / 2;

 

int min = -2000000000; int max = -2000000000;

int sum = 0;

 

for (int i = mid; i >= 0; i--)

{

sum += arr[i];

min = ( min > sum) ? min : sum;

}

sum = 0;

 

for (int j = mid+1; j <= right; j++)

{

sum += arr[j];

max = (max > sum) ? max : sum;

}

 

int p = cal(arr, left, mid);

int q = cal(arr, mid + 1, right);

 

int result = (p > q) ? p : q;

 

return (min + max > result) ? min + max : result;

}

////////////////////////////////////////

로그형을 취하기 위해, 일단 2개씩 계속해서 나눠 재귀로 구현해봤다.

 배열을 mid기준으로 계속해서 나눈다. left==right가 되면, arr[left]를 반환한다.

 이때, int min과 max를 선언한다. 각자, mid기준으로 왼쪽의 값과 오른쪽의 값중 합의 최대를 뜻한다. 따라서, min은 mid를 기준으로, 0부터 mid까지의 arr의 값을 다 더해가면서 가장 큰 것을 뜻하게 된다. 가장 큰 값이 나와야 해당 값을 그 뒤의 수가 가지고 가야 하기 때문이다. 마찬가지로 max도 mid+1부터 right까지의 가장 큰 값을 나타낸다.

 이때, min을 구하면서 선언을 mid에서 점차 0까지 줄이는 이유는, 오른쪽max값과 연결시키기 위함이다.

 이렇게 한 다음, 구해진 min과 max를 더하면 지정된 구역에서 연결된 가장 큰 값이 나온다. 그 다음, 연결된 구간이 아닌, 다른 폐쇄된 구간에서 따로 더 큰 값이 나왔을 수도 있으므로, mid를 기준으로 나뉘어 폐쇠된 p와 q(left~mid, mid+1~right)중 더 큰 값을 result에 넣은 다음, 해당 값 result와 min+max를 비교해 더 큰 값을 반환한다.

 

난 아가라 사칙연산만 할줄알고 로그할줄 모름