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

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

Đề bài

Cho mảng số nguyên $A$ gồm $n$ phần tử. Hãy chọn hai phần tử ở hai 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:

• $2 \le n \le 10^4$
• $|A_i| \le 10^4$

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

20

Giải thích:

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

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 hai số chỉ có thể là:

• tích hai số lớn nhất (hai số dương lớn), hoặc
• tích hai số nhỏ nhất (hai số âm có trị tuyệt đối lớn: âm × âm = dương).

Một vòng lặp tìm lon1 >= lon2 và nho1 <= nho2 (ở các vị trí khác nhau), đáp án là max(lon1 * lon2, nho1 * nho2). Độ phức tạp $O(n)$.

Ví dụ $-10, -10, 1$: lon1·lon2 = 1·(-10) = -10, nho1·nho2 = 100 → $100$.

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

• Chỉ lấy tích hai số lớn nhất – sai khi có hai số âm rất nhỏ.
• Khởi tạo đáp án bằng 0 – sai khi tích lớn nhất là số âm (ví dụ $-5, 6$ → $-30$).
• Lấy bình phương một phần tử (dùng một phần tử hai lần) – đề yêu cầu hai vị trí khác nhau.
• Chọn hai số có trị tuyệt đối lớn nhất – có thể khác dấu, cho tích âm.
• Duyệt mọi cặp $O(n^2)$ bằng Python sẽ quá thời gian 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 😇