A[0] = -3
A[1] = 1
A[2] = 2
A[3] = -2
A[4] = 5
A[5] = 6배열이 있을 때 A[P] * A[Q] * A[R] (0 ≤ P < Q < R) 를 만족하는 최대값을 구하는 문제인데
이거 퀵 소트로 정렬해보면 -3,-2,1,2,5,6 인데말야 여기서 최대값을 구하려면 맨 끝의 배열 3개만 곱하면 된다고 생각했는데 말야
생각해 보니 -가 두개 곱해져서 더 큰 값이 나올 때가 있을 것 같더라고 여기서 어떻게 해야해?
시간복잡도는 (NlogN) 에서 끝내라니까 for문 3개 돌릴수도 없고 ㅠㅠ
세칸짜리배열에당고빼면서훑고지나가면끝
배열에 음수가 몇 개 있는지 모른다고 가정할 때 퀵소트하고 앞3개, 뒷3개, 앞1개*뒤2개, 앞2개*뒤1개 네 개 중에 비교하면 되지 않을까요 ^_^
아니다 뒤1개 앞2개나 뒤3개는 안넣어도 됨 빠가잼^_^
테스트