Buổi 10: Các thuật toán trên dãy

1. Kiến thức chính

Tìm lớn nhất và vị trí

mx = a[0]               # KHÔNG khởi tạo mx = 0 (sai khi dãy toàn số âm)
vt = 0
for i in range(1, n):
    if a[i] > mx:
        mx = a[i]
        vt = i
print(mx, vt + 1)       # vị trí đánh số từ 1

Hàm có sẵn được dùng khi đi thi: max(a), min(a), sum(a), a.count(x), a.index(x).

Biến cờ – kiểm tra "mọi phần tử đều …"

tang = True                    # 1. giả sử dãy tăng
for i in range(1, n):
    if a[i] <= a[i - 1]:       # 2. tìm phản ví dụ
        tang = False           # 3. hạ cờ
        break

Duyệt mọi cặp (i < j)

for i in range(n):
    for j in range(i + 1, n):  # j bắt đầu từ i + 1: mỗi cặp xét một lần
        ...

Có khoảng n² ÷ 2 cặp: n = 1000 thì kịp, n = 10⁵ thì không kịp.

Đoạn liên tiếp dài nhất

best = hien_tai = 1
for i in range(1, n):
    if a[i] > a[i - 1]:
        hien_tai += 1          # bậc thang tiếp tục
    else:
        hien_tai = 1           # bắt đầu lại
    best = max(best, hien_tai)

Chỉ duyệt dãy một lần nên chạy nhanh kể cả khi n = 10⁵.

2. Ghi nhớ và lỗi thường gặp

3. Câu hỏi tự kiểm tra

1. Vì sao khởi tạo mx = a[0] tốt hơn mx = 0?
2. Với n = 5, hai vòng lặp for i in range(n) và for j in range(i + 1, n) xét tất cả bao nhiêu cặp?
3. Trong dãy 4 4 4, đoạn tăng chặt liên tiếp dài nhất có độ dài bao nhiêu?

4. Bài tập về nhà

Định dạng input chung (trừ khi ghi khác): dòng 1 là n (1 ≤ n ≤ 10⁵), dòng 2 là n số nguyên (|aᵢ| ≤ 10⁹).

Bài 1 ★★ – DEMDINH

Phần tử aᵢ (không phải đầu dãy, không phải cuối dãy) là đỉnh nếu nó lớn hơn cả hai phần tử kề bên.

Output: số đỉnh của dãy.

Bài 2 ★★ – DOANBANG

Output: độ dài đoạn dài nhất gồm các phần tử bằng nhau đứng liên tiếp.

Bài 3 ★★ – CAPSOCONG

Dãy là cấp số cộng nếu hiệu hai số liên tiếp luôn bằng nhau (ví dụ 2 5 8 11).

Output: YES hoặc NO.

Bài 4 ★★★ (thử thách) – LAINHAT

aᵢ là giá một món hàng vào ngày thứ i. Em mua vào một ngày và bán ra vào một ngày sau đó. Tìm tiền lãi lớn nhất (có thể âm nếu ngày nào cũng lỗ).

Input: như trên với n ≥ 2. Output: lãi lớn nhất = max(aⱼ − aᵢ) với i < j.