즉, 배열의 모든 원소를 차례대로 순회를 하는데, 한 변수 (위 코드에서 is_negative)는 지금까지의 값들이 음수였는지를 기록하고, 또 다른 변수 하나 (위 코드에서 is_positive)는 지금까지의 값들이 양수였는지를 기록하는 것이다. 만약 이 두 변수가 모두 false가 되면 부호가 다른 값을 만나는 것이 된다. 왜냐 하면, 다음과 같기 때문이다.
P1: 모든 원소가 양수이다.
Q1: is_positive는 true이다.
P2: 모든 원소가 음수이다.
Q2: is_negative는 true이다.
로 두면 명제 "P1 또는 P2 이면 Q1 또는 Q2 이다"의 대우는
" NOT(Q1 OR Q2) 이면 NOT(P1 AND P2)이다"
이고, 이것은, 다시
"NOT Q1 AND NOT Q2 이면 NOT P1 OR NOT P2이다"
가 된다. 따라서,
" is_positive와 is_negative가 둘 다 false 이면 (모든 원소가 양수는 아니고) 혹은 (모든 원소가 음수는 아니다) " 가 된다. 즉,
" is_positive와 is_negative가 둘 다 false 이면 (양수 중에 음수가 적어도 하나 있다) 혹은 (음수 중에 적어도 하나 양수가 있다)" 가 되고, 이것은 결국
" is_positive와 is_negative가 둘 다 false 이면 양수와 음수가 섞여 있다"
가 되기 때문이다.
원소가 (v1, ..., vn) 이 있을 때, sign(v_i) == sign(v_{i+1}) for all i = 1, ..., n-1 only if sign(v_i) == sign(v_j} for all 1 <= i, j <= n 이 맞는지를 확인해 보면 된다. Let sign(v_i) == sign(v_{i+1}) for all i = 1, ..., n-1 (1). Suppose that ∃ i < j such that sign(v_i) ≠ sign(v_j). If i - j = 1, then it contradicts to (1). Therefore, there must be (a_1, ..., a_m) such that i < (a_1, ..., a_m) < j. By (1), sign(v_i) == sign(v_{a_1}). By the induction, sign(v_{a_m}) == sign(v_j), which is contradiction. Q.E.D.
조금 쉽게, 다시 설명하면, 우리가 알아 보고자 하는 것은, 모든 인접한 두 원소의 부호가 같을 때, 전체 원소가 모두 같은 부호를 갖고 있는가? 이다. 즉, i 번째 부호와 i+1 번째 부호가 모든 i 에 대하여 같았을 때, 어느 두 원소를 선택해도 부호가 같을 것인가? 이다. 모든 i 에 대하여 i 번째와 i+1 번째의 부호가 같았는데(1), 어느 두 원소를 뽑았더니 부호가 다른 원소가 있었다고 가정해 보자. 그 각각의 원소의 인덱스를 a 와 b라고 하고, a 가 더 작은 값이라고 하자. 만약 a == b + 1 이었다면 (1)에 모순되기 때문에 말이 안되므로 a 와 b 사이에는 몇 개의 정수가 들어 갈 수 있게 되서, (a, a+1, ..., b-1, b) 의 sub-sequence를 만들 수 있게 된다. (1)에 의해 a 번째와 a+1 번째 원소의 부호는 같아야 하며, 같은 식으로 계속 해나가다 보면 b-1번째와 b번째의 부호도 같아야 하고, 따라서 a 번째부터 b번째의 원소의 부호는 모두 같다. 그런데 이것은 가정에 모순이므로, 모든 i 에 대하여 i 번째와 i+1 번째의 부호가 같았는데, 어느 두 원소를 뽑았더니 부호가 다른 원소가 있을 수는 없다. 즉, 모든 i 에 대하여 i 번째와 i+1 번째의 부호가 같다면 모든 원소의 부호가 같다.
그런데, 좀 더 생각을 해보면, 아주 간단하게는 모든 원소의 부호가 첫 번째 원소의 부호와 같으면 된다. 증명은 쉽고, 코드도 쉽다... >.<"" 어려운 문제인 줄 알았는데... ㅋㅋㅋ 두 실수 (a,b)에 대하여 relation R을 부호의 같음으로 정의하면 R은 equivalence relation 이 되기 때문에.
