Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18]
,
The longest increasing subsequence is [2, 3, 7, 101]
, therefore the length is 4
.
Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2
) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
class Solution {
func lengthOfLIS(nums: [Int]) -> Int {
guard nums.count != 0 else {
return 0
}
var lengths = Array(count: nums.count, repeatedValue: 1)
for i in 0 ..< nums.count {
for j in 0 ..< i {
if nums[i] > nums[j] {
if lengths[i] < lengths[j] + 1 {
lengths[i] = lengths[j] + 1
}
}
}
}
return lengths.reduce(0) { (a, b) -> Int in
a > b ? a : b
}
}
}
网友评论