두 수열

각 수열에서 필요한 정보는 최솟값과 최댓값뿐이다.

어떤 수 $x$를 다른 수열의 원소와 곱한다고 하자. $x$가 양수이면 곱을 크게 만들기 위해서는 상대 수열의 최댓값을 고르는 것이 최적이다. $x$가 음수이면 곱을 크게 만들기 위해서는 상대 수열의 최솟값을 고르는 것이 최적이다. $x=0$인 경우도 최솟값과 최댓값 후보 안에서 함께 처리된다.

따라서 최적해는 다음 네 값 중 하나이다.

$$\min(A)\min(B),\quad \min(A)\max(B),\quad \max(A)\min(B),\quad \max(A)\max(B)$$

네 값의 최댓값을 출력하면 된다. 시간 복잡도는 $O(N)$이고, 메모리 복잡도는 $O(1)$이다.