Cho một dãy số A gồm 𝑛 số nguyên 𝑎1, 𝑎2, … , 𝑎𝑛. Yêu cầu: Hãy tìm ba vị trí 𝑘, 𝑖 và 𝑗 (0 < 𝑘 < 𝑖 < 𝑗 ≤ 𝑛) sao cho giá trị biểu thức ak-2ai+3aj là lớn nhất. Dữ liệu: Vào từ tệp văn bản BAI4.INP có

Để giải bài toán này, ta cần tìm ba chỉ số \(k\), \(i\) và \(j\) sao cho \(0 < k < i < j \leq n\) và giá trị biểu thức \(a_k - 2a_i + 3a_j\) là lớn nhất.

### Phân tích bài toán

1. Dạng biểu thức: Xét biểu thức \(a_k - 2a_i + 3a_j\). Để tìm ra giá trị lớn nhất, ta cần riêng biệt tối đa hóa các thành phần của biểu thức này.

2. Tình huống nhiều chỉ số: Ta có ba chỉ số mà điều kiện thứ tự phải tuân thủ, do đó ta không thể kiểm tra một cách brute force cho tất cả các hoán vị ba chỉ số này từ \(1\) đến \(n\), vì điều đó sẽ mất nhiều thời gian (thời gian thực hiện sẽ là \(O(n^3)\)).

### Kỹ thuật tiếp cận

- Biến đổi biểu thức: Đặt lại biểu thức thành dạng khác để dễ dàng tối ưu. Thay vì tối ưu hóa ba chỉ số riêng biệt, ta có thể tối ưu theo từng chỉ số trong một vòng lặp.

- Tìm cách tối ưu hóa từng thành phần:
- Để tìm giá trị lớn nhất của biểu thức, ta có thể giữ cố định một trong ba chỉ số và tối ưu cho hai chỉ số còn lại.
- Cụ thể, với từng giá trị của \(i\):
- Tính \(a_k\) cho mọi \(k < i\).
- Tính \(a_j\) cho mọi \(j > i\).

- Tối ưu giá trị của \(a_k\):
- Trong khi duyệt qua chỉ số \(i\), ta có thể giữ một biến để lưu giá trị \(a_k\) lớn nhất mà đã được tính ở những bước trước.

- Tối ưu giá trị của \(a_j\):
- Ta cũng có thể tính toán giá trị \(a_j\) bằng cách duyệt từ phải sang trái để lưu giá trị lớn nhất của các \(a_j\).

### Thuật toán

1. Khởi tạo một biến `max_value` để lưu giá trị tối đa của biểu thức.
2. Tạo một danh sách `max_k` với kích thước \(n+1\) để lưu trữ giá trị lớn nhất của \(a_k\) cho mọi chỉ số \(i\).
3. Duyệt từ trái qua phải để cập nhật giá trị lớn nhất của \(a_k\).
4. Duyệt từ \(i = 1\) đến \(n - 2\) (vì \(i\) không thể ở đầu hay cuối):
- Tính giá trị của \(2a_i\).
- Sử dụng `max_k` để tìm giá trị lớn nhất của \(k\) cho chỉ số hiện tại.
- Duyệt từ \(j = i + 1\) đến \(n\) để cập nhật giá trị của biểu thức \(3a_j\).
5. Cập nhật `max_value` nếu tìm thấy giá trị tốt hơn.

### Mã giả

```python
# Đọc dữ liệu
n = int(input())
A = list(map(int, input().split()))

# Khởi tạo
max_k = [0] * n
max_value = float('-inf')

# Cập nhật max_k
max_k[0] = A[0]
for i in range(1, n):
max_k[i] = max(max_k[i - 1], A[i])

# Tính giá trị tối đa
for i in range(1, n - 1):
current_value = -2 * A[i]
current_k = max_k[i - 1] # giá trị max_k cho k
for j in range(i + 1, n):
value = current_k + current_value + 3 * A[j]
max_value = max(max_value, value)

# Xuất kết quả
print(max_value)
```

### Kết luận

Giá trị tối đa của biểu thức \(a_k - 2a_i + 3a_j\) có thể đạt được thông qua kỹ thuật duyệt và lưu trữ giá trị tối ưu cho từng chỉ số, điều này giúp chúng ta giảm thiểu thời gian với độ phức tạp gần \(O(n^2)\) trong trường hợp tốt nhất và \(O(n)\) cho việc tìm kiếm giá trị tối đa cho các phần tử một cách hiệu quả.