Bài 11.3. Kho Báu Đồ Họa - [Độ khó: Khó]

Mô tả bài tập: Bạn là một nhà thám hiểm đang khám phá một khu hầm cổ, nơi các bức tường được trang trí bằng những bức tranh quý giá. Mỗi bức tranh có một chiều cao khác nhau, và chúng được sắp xếp thành một hàng (có thể coi là một biểu đồ cột - histogram). Để vận chuyển kho báu, bạn cần tìm một khu vực hình chữ nhật lớn nhất có thể được "cắt" ra từ bức tường, mà không làm hỏng bất kỳ bức tranh nào. Khu vực này phải được tạo thành từ các bức tranh liền kề, và chiều cao của nó bị giới hạn bởi bức tranh thấp nhất trong khu vực đó. Nhiệm vụ của bạn là tìm diện tích lớn nhất của khu vực hình chữ nhật này.

INPUT FORMAT Dòng đầu tiên chứa một số nguyên N (1 <= N <= 10^5) là số lượng bức tranh. Dòng thứ hai chứa N số nguyên h_1, h_2, ..., h_N (0 <= h_i <= 10^9) là chiều cao của các bức tranh.

OUTPUT FORMAT In ra một số nguyên duy nhất là diện tích hình chữ nhật lớn nhất tìm được.

Ví dụ: Input:

7
6 2 5 4 5 1 6

Output:

12

Giải thích:

• Mảng chiều cao: [6, 2, 5, 4, 5, 1, 6]
• Ta xét tất cả các khả năng tạo hình chữ nhật và tính diện tích của chúng:
  • Nếu chọn bức tranh có chiều cao h = 4 (tại chỉ số 3) làm chiều cao của hình chữ nhật:
    • Ta có thể mở rộng sang trái đến bức tranh có chiều cao 5 (tại chỉ số 2) và sang phải đến bức tranh có chiều cao 5 (tại chỉ số 4).
    • Dãy con này là [5, 4, 5]. Chiều cao nhỏ nhất trong dãy này là 4.
    • Độ dài của dãy con này là 3 bức tranh.
    • Diện tích hình chữ nhật tạo thành: 4 * 3 = 12.
  • Nếu chọn bức tranh có chiều cao h = 2 (tại chỉ số 1) làm chiều cao của hình chữ nhật:
    • Ta có thể mở rộng sang trái đến bức tranh có chiều cao 6 (tại chỉ số 0) và sang phải đến bức tranh có chiều cao 5 (tại chỉ số 4).
    • Dãy con này là [6, 2, 5, 4, 5]. Chiều cao nhỏ nhất trong dãy này là 2.
    • Độ dài của dãy con này là 5 bức tranh.
    • Diện tích hình chữ nhật tạo thành: 2 * 5 = 10.
  • Tương tự, ta kiểm tra tất cả các trường hợp khác.
• Diện tích lớn nhất tìm được là 12.