Question

How to find the longest increasing not sorted subsequence (LIS) of a sequence of numbers in Swift

Answer 1

func longestIncreasingSubsequence(_ nums: [Int]) -> Int {
    guard !nums.isEmpty else { return 0 }

    var lengths = Array(repeating: 1, count: nums.count)
    var maxLength = 1

    for i in 1..<nums.count {
        for j in 0..<i {
            if nums[i] > nums[j] {
                lengths[i] = max(lengths[i], lengths[j] + 1)
            }
        }
        maxLength = max(maxLength, lengths[i])
    }

    return maxLength
}

let nums = [4, 5, 1, 10, 3, 9, 18, 19]

print("Length of LIS: \(longestIncreasingSubsequence(nums))")



/*
run:

Length of LIS: 5

*/

 

70+ SQL courses for beginners and professionals