Imagine there are n people in a line, which every one of them has there unique value for themselves from 1 to n, we try to sort them like this:
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
As you see, with each swap there goes a friendship between them, and for a person, if they didn't get swapped with another person, there won't be any friendship between them, the question is after the operation is done for an input, what the maximum number of people who are not friends ?! Example input:
3
3 1 2
Example output:
2
I tried to solve this problem using this code:
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)
which works great for all the inputs and gives us the right answer as I checked, but it has a time complexity of O(n^3) which totally not great for large inputs. Is there a way to optimize this code ?! Or at least there is another solution and approach to this ?! This code assumes that with each swap, an edge from a complete graph with n vertices gets removed and with this have in mind, there will be edges between two indexes of permutation if and only if the index that is higher than the other has higher value.
So the problem is actually solved if we try to find the Longest Increasing Subsequent (LIS), with that said, we don't even need to execute the algorithm at all. The code for answering the question would be something like this:
n = int(input())
permutation = list(map(int, input().split()))
dp = []
for i in range(n):
low, high = 0, len(dp)
while low < high:
mid = (low + high) // 2
if dp[mid] < permutation[i]:
low = mid + 1
else:
high = mid
if low == len(dp):
dp.append(permutation[i])
else:
dp[low] = permutation[i]
print(len(dp))
To describe this code in short, it iterates on the elements and makes an array with the respect to the order of the elements in the original array, that is increasing, and it will become the longest one because we consider each element and modify the dp array (which will be the array of Longest increasing subsequent) respectively. The length of dp array will be our answer.