Given n integers x 1 ,x 2 ,...,x n . Delete from them the least number of integers…
- User
Given n integers x 1 ,x 2 ,...,x n . Delete from them the least number of integers so that the rest were in ascending order.
Input The first line contains the number n (1≤n≤10 5 ). The second line contains the integers x 1 ,x 2 ,...,x n (1≤x i ≤60000).
Output Print in the first line the number of not erased integers. In the second line print the list of unerased integers in the original order. If several answers exist, print any.
Examples Input #1 6 2 5 3 4 6 1 Answer #1 4 2 3 4 6 Ən asan yolu ilə yaz
- Assistant
To solve the problem of finding the longest increasing subsequence (LIS) from a list of integers, we can use a dynamic programming approach with binary search to ensure an efficient solution that works within the given constraints.
Approach:
-
Dynamic Programming with Binary Search:
- We maintain an array
tailswheretails[i]represents the smallest possible tail value of an increasing subsequence of lengthi+1. - For each number in the input array, we use binary search to find the position in the
tailsarray where this number can either extend the subsequence or replace an existing value to maintain the smallest possible tail. - We also maintain an array
prevto keep track of the predecessors of each element in the subsequence, which helps in reconstructing the LIS at the end.
- We maintain an array
-
Reconstruction of the LIS:
- After processing all elements, the length of the
tailsarray gives the length of the LIS. - We then backtrack using the
prevarray to reconstruct the actual subsequence.
- After processing all elements, the length of the
Implementation in Python:
import sys import bisect def main(): import sys sys.setrecursionlimit(1 << 25) input = sys.stdin.read lines = input().split() n = int(lines[0]) x = list(map(int, lines[1:n+1])) tails = [] indices = [] prev = [-1]*n for i in range(n): num = x[i] # Find the insertion point using binary search pos = bisect.bisect_left(tails, num) if pos == len(tails): tails.append(num) indices.append(i) else: tails[pos] = num indices[pos] = i if pos >0: prev[i] = indices[pos-1] length = len(tails) # Reconstruct the sequence by backtracking seq = [] k = indices[-1] for _ in range(length): seq.append(x[k]) k = prev[k] seq.reverse() print(length) print(' '.join(map(str, seq))) if __name__ == "__main__": main()Explanation of the Code:
-
Input Reading:
- The first line contains the number
n. - The second line contains the list of integers.
- The first line contains the number
-
Processing:
- For each integer, determine its correct position in the
tailsarray using binary search. - Update the
tails,indices, andprevarrays accordingly.
- For each integer, determine its correct position in the
-
Reconstruction:
- Starting from the last index of the LIS, backtrack using the
prevarray to build the actual subsequence.
- Starting from the last index of the LIS, backtrack using the
-
Output:
- First, print the length of the LIS.
- Then, print the LIS itself in the original order.
Example:
Input:
6 2 5 3 4 6 1Output:
4 2 3 4 6This output corresponds to one of the possible longest increasing subsequences from the input list.
-