44 lines
914 B
Swift
44 lines
914 B
Swift
func solve() -> Int {
|
|
guard let N = Int(readLine() ?? ""),
|
|
let input = readLine()
|
|
else { return 0 }
|
|
|
|
let A: [Int] = input.split(separator: " ").compactMap{Int($0)}
|
|
if A.count != N { return -1 }
|
|
|
|
var LIS: [Int] = []
|
|
|
|
for now in A {
|
|
if LIS.isEmpty {
|
|
LIS.append(A[0])
|
|
continue
|
|
}
|
|
|
|
guard let lastNum: Int = LIS.last else { break }
|
|
|
|
if lastNum < now {
|
|
LIS.append(now)
|
|
}
|
|
else {
|
|
var l = 0, r = LIS.count-1
|
|
|
|
while l < r {
|
|
let mid: Int = (l+r)/2
|
|
|
|
if LIS[mid] < now {
|
|
l = mid + 1
|
|
}
|
|
else {
|
|
r = mid
|
|
}
|
|
}
|
|
|
|
LIS[l] = now
|
|
}
|
|
}
|
|
|
|
return LIS.count
|
|
}
|
|
|
|
print(solve())
|