Maximum Subarray problem

Proof using 'cut and paste'

우리가 보이고 싶은 명제는
"전체 배열의 maximum subarray는

1. 왼쪽 부분 배열의 maximum subarray
2. 오른쪽 부분 배열의 maximum subarray
3. mid를 가로지르는 maximum subarray

위 세 가지 중 하나이다."

전체 배열의 최적해 A[i...j]를 하나 잡았다고 하자.

1. 최적해의 원소들이 전부 mid보다 왼쪽 구간에 있으면 A[i...j]는 왼쪽 부분배열 안에서의 maximum subarray이다.
   • 만약 왼쪽 구간에 A[i...j]보다 합이 더 큰 부분배열 A[p...q]가 존재한다면
   • 이는 기존 최적해 A[i...j]를 A[p...q]로 잘라 붙여 더 큰 합의 해를 만들 수 있기 때문에 A[i...j]가 최적해라는 가정에 모순이 된다.
   • 따라서 A[i...j]는 왼쪽 부분배열의 maximum subarray이다.

2. 최적해의 원소들이 전부 mid보다 오른쪽 구간에 있으면 A[i...j]는 오른쪽 부분배열 안에서의 maximum subarray이다.
   • 만약 오른쪽 구간에 A[i...j]보다 합이 더 큰 부분배열 A[p...q]가 존재한다면
   • 이는 기존 최적해 A[i...j]를 A[p...q]로 잘라 붙여 더 큰 합의 해를 만들 수 있기 때문에 A[i...j]가 최적해라는 가정에 모순이 된다.
3. 최적해의 원소들중 mid를 지나는 원소가 있다면, A[i...j]는 crossing array중 maximum subarray이다.
   • crossing 최적해 A[i...j]는 왼쪽은 mid에서 끝나는 최대 suffix, 오른쪽은 mid+1에서 시작하는 최대 prefix의 결합이다.
   • 만약 A[i...mid]보다 합이 더 큰 suffix A[p...mid]가 존재한다면
   • A[i...j]를 A[p...j]로 교체할 수 있다.
   • 이는 기존 최적해 A[i...j]보다 더 큰 합의 해를 만들 수 있기 때문에 A[i...j]가 최적해라는 가정에 모순이 된다.
   • 따라서 A[i...mid]는 최대 suffix이다.
   • 마찬가지로, 만약 A[mid+1...j]보다 더 큰 prefix A[mid+1...q]가 존재한다면
   • A[i...j]를 A[i...q]로 교체할 수 있으므로 가정에 모순이다.
   • 따라서 A[i...mid]는 mid에서 끝나는 최대 suffix, A[mid+1...j]는 mid+1에서 시작하는 최대 prefix 형태이며, 따라서 이는 crossing subarray들중 maximum subarray이다.

---

MSP in Linear time

#include <iostream>
using namespace std;

int main() {
	int arr[11] = { 0, 2, -3, 5, -1, -2, -4, 10, 7, -2, -3};

	int thisSum = 0;
	int maxSum = 0;
	for (int i = 1; i <= 10; i++) {
		thisSum += arr[i];
		if (thisSum > maxSum) {
			maxSum = thisSum;
		}
		else if (thisSum < maxSum) {
			thisSum = 0;
		}
	}

	cout << maxSum;

	return 0;
}

• linear time의 장점

1. 메모리 효율
   • 스트리밍처럼 한 번 쭉 읽으면서 처리가 가능하기 때문에
   • 배열 전체를 메모리에 다 올릴 필요가 없다.
   • 데이터를 앞에서부터 한 번씩만 읽으면서 처리 가능하다.
2. 실시간 처리 (Online)
   • 데이터를 끝까지 다 보지 않아도, 지금까지 읽은 부분에 대해서는 항상 정답을 알고 있다.
   • 즉, 중간 과정에서도 항상 지금까지의 정답이 유지되고 있다.