Chương trình tìm danh sách "núi" lớn nhất theo thứ tự từ điển trong Python

Cho ba số dương n, lower, upper. Tìm danh sách độ dài n tăng chặt rồi giảm chặt, mọi phần tử trong [lower, upper], cả phần tăng và giảm đều không rỗng. Trả về danh sách lớn nhất theo thứ tự từ điển (lexicographically largest), hoặc rỗng nếu không tồn tại.

Ví dụ: n = 5, lower = 3, upper = 7 → kết quả [6, 7, 6, 5, 4]. Lưu ý [7,6,5,4,3] không hợp lệ vì phần tăng rỗng.

Thuật toán giải quyết

1. Nếu n > 2*(upper-lower) + 1: trả về [] (không đủ phạm vi)
2. c = upper - lower, d = 1
3. Nếu c < n: d = n - c - 1
4. Nếu d == 0: d = 1
5. Phần tăng: f = range(upper-d, upper)
6. Phần giảm: g = range(upper, upper-n+d, -1)
7. Trả về f + g

Ví dụ minh họa

def solve(n, lower, upper):
    if n > 2 * (upper - lower) + 1:
        return []
    c = upper - lower
    d = 1
    if c < n:
        d = n - c - 1
    if d == 0:
        d = 1
    f = list(range(upper - d, upper))
    g = list(range(upper, upper - n + d, -1))
    return f + g

n = 5
lower = 3
upper = 7
print(solve(n, lower, upper))

Đầu vào

5, 3, 7

Đầu ra

[6, 7, 6, 5, 4]