오늘 스터디_좋은 문제

n개의 정수가 주어지고, 주어진 순서를 유지하면서 왼쪽, 오른쪽 두 부분으로 나눠서 왼쪽편의 최대값과 오른쪽 편의 최대값의 차이가 최대가 되도록 하는 문제. 시간, 공간 복잡도를 O(n)만에 풀어야 한다.

최대값MAX를 먼저 구한다. 그리고 왼쪽 끝의 수A, 오른쪽 끝의 수B와 비교해본다.
즉, |MAX-A| 와 |MAX-B| 중 더 큰 값이 구하는 차이의 최대이다.
왜냐하면, 일단 MAX가 n개 중에서 최대값이므로 MAX가 포함된 쪽에서는 당연히 MAX가 최대값일 것이고, MAX가 포함되지 않은 쪽에서 최대값을 고르되, 그 최대값이 가장 작아야한다. MAX가 있는 쪽의 범위를 늘려서 다른 쪽의 큰 값들을 MAX가 있는 쪽에 포함되게 만들 수 있지만 수열 양 끝에 있는 값 두 개 중 하나는 포함할 수 없다.
그렇기 때문에, 수열 끝에 있는 값이 한쪽 그룹에서 가장 큰 값이면 어쩔 수 없이 그 값을 한쪽 그룹의 최대값으로 뽑을 수 밖에 없고, 만약 그 그룹에서 끝에 있는 값보다 더 큰 값이 있다면 그 큰 값을 MAX가 있는 쪽의 범위를 늘려서 포함시키면 이제 그 그룹의 최대값은 수열의 끝에 있는 값이 된다.

그러니까... 양 쪽 끝에 있는 값중 하나는 수열을 두 개 그룹으로 나눴을 때 적어도 하나의 그룹에서는 최대값이 될 수 밖에 없거나, 최대값이 되어야 왼쪽 편의 최대값과 오른쪽 편의 최대값의 차이가 최대가 되도록 할 수 있다.

정말 좋은 아이디어인데, 더 중요한 것은 이 아이디어의 정당성을 설명할 수 있는 것이 중요하다. 그리고 위와 같이 풀 경우 시간복잡도 O(n), 공간복잡도 O(1)만에 푸는 것이 된다.