Поиск наиболее оптимального способа обновления массива динамического программирования

Представьте, что в строке находятся n человек, каждый из которых имеет уникальное для себя значение от 1 до n, мы пытаемся отсортировать их следующим образом:

repeat
    swapped = false
    for i from 1 to n do:
        if a[i] > a[i+1] then
            add a friendship between a[i] and a[i+1]
            swap(a[i], a[i+1])
            swapped = true
        end if
    end for
until not swapped

Как видите, при каждом обмене между ними происходит дружба, а для человека, если его не поменяли с другим человеком, никакой дружбы между ними не будет, вопрос в том, после того, как операция будет сделана для вводите, какое максимальное количество людей не в друзьях?! Пример ввода:

3
3 1 2

Пример вывода:

2

Я попытался решить эту проблему, используя этот код:

n = int(input())
permutation = list(map(int, input().split()))
dp = [[] for _ in range(n)]
max_length = 0
for i in range(n):
    dp[i].append(i)
    for j in range(i):
        if permutation[j] < permutation[i]:
            addable = True
            for k in dp[j]:
                if (permutation[k] > permutation[i] and k < i) or (permutation[k] < permutation[i] and k > i):
                    addable = False
                    break
            if addable and len(dp[j]) + 1 > len(dp[i]):
                dp[i] = dp[j].copy()
                dp[i].append(i)
    if len(dp[i]) > max_length:
        max_length = len(dp[i])

print(max_length)

который отлично работает для всех входных данных и дает нам правильный ответ, как я проверил, но имеет временную сложность O(n^3), что совершенно не подходит для больших входных данных. Есть ли способ оптимизировать этот код?! Или хотя бы есть другое решение и подход к этому?! Этот код предполагает, что при каждой замене ребро из полного графа с n вершинами удаляется, и с учетом этого ребра между двумя индексами перестановки будут тогда и только тогда, когда индекс, который выше другого, имеет более высокое значение. .