Lesson6. Sorting - MaxProductOfThree

MaxProductOfThree - Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).

https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/

문제요약

N개의 정수 배열 A가 있고 triplet (P, Q, R)이 있을 때 A[P] * A[Q] * A[R] (0<=P<Q<R<N)을 product라고 한다. A에서 가장 큰 product를 찾는다.

Assume that:

N is an integer within the range [3..100,000];

each element of array A is an integer within the range [−1,000..1,000].

Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

풀이

임의의 세 수를 선택해서 곱했을 때 가장 큰 수를 만들어야하므로, 양수 중에선는 가장 큰 수 세 수를 선택하면 나머지는 확인 할 필요가 없다. 값의 범위가 음수도 포함되기 때문에 음수의 경우는 가장 작은 음수 2개와 가장 큰 양수 1개를 곱하는 경우를 고려하면 되고 이 두 경우 중 큰 값을 반환하면 된다.