美文网首页
Swift算法:Longest Increasing Subse

Swift算法:Longest Increasing Subse

作者: 我偏笑_NSNirvana | 来源:发表于2016-04-28 21:07 被阅读63次

    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
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:Swift算法:Longest Increasing Subse

          本文链接:https://www.haomeiwen.com/subject/ujuhrttx.html