Longest Increasing Subsequence

Leave a comment

December 1, 2016 by oneOokay

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?

这题不能够用stack,因为不是求“连续的”。用dp来做。(用dp有O(n*n)和O(nlogn)的方法,目前看懂了n *n的。)

dp[] 用来表示从0到当前的index为i的数字的longest increasing subsequence的长度为多少。两个for-loop:

  • 外层循环整个数组:初始化dp[i] = 1: 因为在数组不为null和空的情况下,dp[i]最小值为1.
  • 内层从0开始循环至i -1 :如果当前需要处理的数:nums[i](外层i)小于内层里面某个元素的时候(nums[j]),更新dp[i]:取dp[j] + 1或者当前dp[i]的较大者。同时更新一个int max.

改进的算法:O(nlogn)貌似是把内层的for循环给替换成了binary search,discussion那里同胞们吵起来了=。=也没看几个人给对好的例子,我以后再看吧。


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: