Longest Increasing Subsequence related

Leave a comment

December 1, 2016 by oneOokay

  • Longest Increasing Subsequence
  • Number of Longest Increasing Subsequence

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那里同胞们吵起来了=。=也没看几个人给对好的例子,我以后再看吧。


Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.


需要两个array:

  • 一个length array来存以当前num[i]结尾的LIS的长度;
    • 两个for loop. 外层i从[0, n), 内层从[0, i)寻找LIS length.
  • 另一个count array来存在当前i的位置上LIS的个数.具体看代码
    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] len = new int[n], count = new int[n];
        int maxLen = 1, res = 0; //res初始化为0
//初始化为1.单个元素本身也是一个长度为1的LIS
        for (int i = 0; i < n; i ++){
            len[i] = count[i] = 1; 
            for (int j = 0; j < i; j ++){ 
//从[0,i)对每一个比当前num[i]小的nums[j]进行判断,此时num[i]和num[j]可以组成一个LIS
                    if (nums[i] > nums[j]){
//在j处LIS的个数 + 1 == 在j处的LIS的个数
//说明nums[i]和nums[j](以及nums[j]之前的数字)也能组成一个len[i]的LIS.
//在j之前已经有一个nums[x]和nums[i]组成一个LIS了,且长度为len[i].
//所以count[i]要加上count[j].
                    if (len[i] == len[j] + 1){
                        count[i] += count[j];
                    } else if (len[i] < len[j] + 1){
//更新len[i]和count[j]
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
//维护一个全局的maxLen和res, 就不用最后在loop一遍array找到maxLen和相应的count了
            if (maxLen == len[i]) res += count[i];
            else if (maxLen < len[i]) {
                maxLen = len[i];
                res = count[i];
            }
        }
        return res;
    }

 

Advertisements

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: