1.1 Maximum Range Sum (1)

Maximum Range Sum이란 길이가 n인 배열을 받아서 구간을 잡아 그 구간에 있는 모든 배열 값을 더해서 그 값이 최대가 되도록 하는 값을 찾도록 하는 문제이다.

그냥 바로 생각하면 배열의 모든 값을 더하면 최댓값이 될 수 있다고 생각할 수도 있지만, 이렇게 하려면 배열의 모든 값이 양수라는 조건이 있어야 한다. 즉, 임의의 숫자에 대해서는 이렇게 생각할 수 없다는 것이다.

그러면 이 문제를 어떻게 하면 해결 할 수 있을까? 가장 간단한 방법은 모든 구간에 대해서 Range Sum을 계산해서 그 값을 계속 비교해나가면서 최대인 것을 선택해서 그 값을 반환해주면 된다.

이제 이것을 C++ 코드로 작성하면 아래와 같다.

int getMaximumRange1(int *arr, int size){
	int max = INT_MIN;
	for(int i=0; i<size; i++){
		for(int j=i; j<size; j++){
			int sum = 0;
			for(int k=i; k<=j; k++)
				sum += arr[k];
			if(max < sum)
				max = sum;
		}
	}
	return max;
}

코드에 대해 약간 설명하자면 구간 [i, j]에서의 Range Sum을 계산해서 그 값과 이전의 max로 저장해놓은 값과 비교해서 더 큰 값을 max로 업데이트를 하는 방식으로 구현하였다. 그리고 이 코드를 직접 실행해보려면 INT_MIN 부분 때문에 climits 헤더가 필요하다.

이 코드에서 배열의 길이가 n일 때의 Time Complexity를 확인해보면, $\sum_{i=0}^{i=n-1} {\sum_{j=i}^{j=n-1}} {(j-i+1)}=O(n^3)$ 이라는 것을 계산을 통해 알 수 있다.

아무래도 그냥 Live하게 코드를 작성한 결과 $O(n^3)$인데, 어떻게 하면 이것을 좀 더 빠른 방법으로 바꿀 수 있을까? 소스코드를 잘 살펴보면 비효율적인 부분이 보일 수도 있다. 이 내용은 다음 내용에서 살펴보도록 하겠다.