冒泡排序衍生最大非好友组问题：O(n³)动态规划解法优化

问题描述 #

假设有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

现有解法与问题 #

我使用了如下时间复杂度为O(n³)的动态规划代码求解，该代码能正确输出结果，但无法处理大规模输入：

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)

我的思路是：将每次交换视为移除完全图中的一条边，最终两人存在好友关系当且仅当原排列中索引更大的元素数值也更大。请问是否存在优化该代码的方法，或者其他更优的解题思路？

内容的提问来源于stack exchange，提问作者FrOZEn_FurY