Shulou(Shulou.com)06/01 Report--

Editor to share with you golang leetcode browsing skills how to achieve the longest ascending sub-sequence, I hope you will gain something after reading this article, let's discuss it together!

Given an unordered array of integers, find the length of the longest ascending subsequence.

Example:

Input: [10, 9, 2, 5, 3, 7, 101, 18]

Output: 4

Explanation: the longest ascending subsequence is [2Jing 3jue 7101], and its length is 4.

Description:

There may be a combination of the longest ascending subsequences, and you only need to output the corresponding length.

The time complexity of your algorithm should be O (N2).

Advanced: can you reduce the time complexity of the algorithm to O (n log n)?

Ideas for solving the problem:

Solution 1: dynamic programming

1, marked by DP [I], the maximum length of the I position

2, the state transition equation is dp [I] = max (DP [j] + 1), j > = 0j

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.