Kiểm tra đảo ngược một mảng con có làm mảng sắp xếp trong Python

Cho mảng nums các phần tử duy nhất. Kiểm tra xem có thể đảo ngược một mảng con nào đó để mảng toàn thể trở thành sắp xếp tăng dần hay không (nếu đã sắp xếp cũng trả về True).

Ví dụ: [4,6,27,25,15,9,37,42] → đảo mảng con [9,15,25,27] → mảng sắp xếp → True.

Giải thuật

• Tìm chỉ số i đầu tiên mà nums[i-1] > nums[i] (bắt đầu đoạn giảm).
• Tìm chỉ số j cuối cùng của đoạn giảm liên tiếp.
• Kiểm tra điều kiện nối: phần tử tại j phải ≥ phần tử trước đoạn giảm (nếu có).
• Kiểm tra phần còn lại sau j đã sắp xếp tăng.

Mã ví dụ

def solve(nums):
    n = len(nums)
    if n == 1:
        return True
    i = 1
    for i in range(1, n):
        if nums[i - 1] < nums[i]:
            if i == n:
                return True
            else:
                break
    j = i
    while j < n and nums[j] < nums[j - 1]:
        if i > 1 and nums[j] < nums[i - 2]:
            return False
        j += 1
    if j == n:
        return True
    k = j
    if nums[k] < nums[i - 1]:
        return False
    while k > 1 and k < n:
        if nums[k] < nums[k - 1]:
            return False
        k += 1
    return True

nums = [4,6,27,25,15,9,37,42]
print(solve(nums))

Đầu vào

[4,6,27,25,15,9,37,42]

Đầu ra

True