Question: How to find the longest increasing subsequence in Swift?
Answer:
func longestIncreasingSubsequence(nums: [Int]) -> [Int] {
var dp = Array(repeating: 1, count: nums.count)
var result = [Int]()
for i in 0..<nums.count {
for j in 0..<i {
if nums[i] > nums[j] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
var maxLength = dp.max()!
for i in (0..<dp.count).reversed() {
if dp[i] == maxLength && (result.isEmpty || nums[i] < result.last!) {
result.append(nums[i])
maxLength -= 1
}
}
return result.reversed()
}
let nums = [10, 9, 2, 5, 3, 7, 101, 18]
let lis = longestIncreasingSubsequence(nums: nums)
print(lis) // prints [2, 3, 7, 18]
/*
The Longest Increasing Subsequence (LIS) problem is to find the longest subsequence of a given sequence in which the elements are in increasing order.
The above implementation uses Dynamic Programming to solve the LIS problem. It creates an array "dp" with the same number of elements as the input array. The array is filled with 1s initially.
The outer two for loops iterate through each element in the input array. For each element, it compares it with all the elements before it, if the current element is greater than the element it is comparing with, it updates the value in the dp array at that position to the maximum value of the position before it + 1.
The next part of the code is to retrace the steps taken to fill the dp array, starting from the end of the array. It appends the element to the result array whenever dp[i] is equal to maxLength and the current element is smaller than the last element in the result array.
This algorithm has a time complexity of O(n^2) where n is the number of elements in the input array, and a space complexity of O(n) for creating the dp array.
*/
Sign up here with your email
ConversionConversion EmoticonEmoticon