Giải thuật: Quy hoạch động.

Giải thuật độ phức tạp ~O(n^2)~:

• Với mỗi mặt hàng ~i (i = 1 \div n-1) ~ tìm ~max \{a_i+a_j \}~ với mọi ~j = i+1 \div n ~ và thỏa mãn điều kiện ~a_i+a_j ≤ x~, lưu ~max~ tìm được vào ~b_i~,

• Đưa ra kết quả ~max\{b_i\}, i =1 \div n~.

Lưu ý: Nếu tìm thấy một ~b_i = x~ thì không cần tính các giá trị còn lại của mảng ~b~.

Giải thuật độ phức tạp ~O(nlnn)~:

Nhận xét:

• Chỉ cần thực hiện mở rộng sơ đồ tìm kiếm max một lần khi chuyển từ chọn một mặt hàng sang chọn ~2~ mặt hàng,
• Không cần duyệt hết danh sách các mặt hàng còn lại nếu giá của chúng đã được sắp xếp,
• Không cần thiết phải lưu các giá trị max trung gian trong quá trình tìm kiếm.

Xử lý:

• Nhập dữ liệu,
• Sắp xếp mảng ~a~ theo thứ tự tăng dần,
• Chuẩn bị: ~ans = -1~ ( lưu ~max~), ~j = n~ (mặt hàng thứ ~2~),
• Với mọi ~i = 1 \div n-1~:
  • Chừng nào có ~j >i~: Lùi ~j~ cho đến khi gặp mặt hàng có thể mua cùng mặt hàng ~i~,
  • Chỉnh lý ~ans~,
• Đưa ra kết quả.