Swift算法（Longest|Swift算法：Longest Increasing Subsequence）
【Swift算法（Longest|Swift算法：Longest Increasing Subsequence）】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
}
}
}
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- Swift中willSet和didSet的简述
- 《算法》-图[有向图]
- Hacking|Hacking with iOS: SwiftUI Edition - SnowSeeker 项目（一）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列