Tích lớn nhất của ba phần tử (VT15)

Nguồn: CLUE OJ Độ khó: Trung bình Mảng 1 chiều Mã bài VT15

Đề bài

Cho mảng số nguyên $A$ gồm $n$ phần tử. Hãy chọn ba phần tử ở ba vị trí khác nhau sao cho tích của chúng lớn nhất, rồi in ra tích lớn nhất đó.

Dữ liệu vào:

• Dòng đầu tiên là số nguyên $n$.
• Dòng thứ hai gồm $n$ số nguyên $A_1, A_2, \ldots, A_n$, cách nhau bởi dấu cách.

Kết quả:

In ra tích lớn nhất tìm được.

Giới hạn:

• $3 \le n \le 10^4$
• $|A_i| \le 1000$

Giới hạn thời gian: 1 giây, bộ nhớ: 512 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

5
1 2 3 4 5

Ví dụ 1 – output

60

Giải thích:

• Chọn $3, 4, 5$, tích $3 \times 4 \times 5 = 60$.
• Lưu ý số âm: với mảng $-10, -10, 1, 2$ thì đáp án là $(-10) \times (-10) \times 2 = 200$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Ý tưởng

Tích lớn nhất của ba số chỉ có hai ứng viên:

• tích ba số lớn nhất lon1 * lon2 * lon3;
• tích số lớn nhất với hai số nhỏ nhất lon1 * nho1 * nho2 (hai số âm nhân nhau thành dương).

Một vòng lặp cập nhật ba số lớn nhất và hai số nhỏ nhất, đáp án là giá trị lớn hơn trong hai ứng viên. Tích tối đa $10^9$, thầy dùng long long cho an toàn.

Ví dụ $-10, -10, 1, 2$: ba số lớn nhất $2 \cdot 1 \cdot (-10) = -20$, còn $2 \cdot (-10) \cdot (-10) = 200$ → $200$.

Lưu ý / bẫy thường gặp

• Chỉ lấy tích ba số lớn nhất – sai khi có hai số âm lớn về trị tuyệt đối.
• Chỉ lấy "số lớn nhất × hai số nhỏ nhất" – sai khi mảng toàn số dương.
• Khởi tạo đáp án bằng 0 – sai khi đáp án âm (ví dụ mảng toàn số âm).
• Chọn ba số có trị tuyệt đối lớn nhất – có thể cho tích âm.
• Duyệt mọi bộ ba $O(n^3)$ quá chậm với $n = 10^4$.

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇