LeetCode(DP)Longest Increasing Subsequence

2018-07-07

Longest Increasing Subsequence

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

Example:

1
2
3

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

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?

思路：这种一看就非常难的题只能用动态规划做了，思路是将这个大问题分成可以存储计算结果的小问题，试着拿一个dp[nums.length]的数组来表示每个以i位置处的数结尾的递增子序列的最大长度。初始每个位置为1。

例子中的[10,9,2,5,3,7,101,18]对应的初始dp[]就是[1,1,1,1,1,1,1,1]，因为加入数组是单调递减的，那么没有任意两个数是递增的，递增的最大单位只有每个数自己本身，这样的情况下每一个数结尾的最长递增子序列的长度都为1.

接着，我们可以比较每一个位置处的nums[i]和它前边的nums[i-1],nums[i-2]…nums[0]的大小关系，只要大于对应的值，我们就比较dp[i]和dp[i-1]+1或dp[i-2]+1或dp[0]+1的大小，取最大的值放入dp[i]。这样计算直到我们遍历完数组中的每一个元素的dp[i]取出其中最大的就是最长递增子序列的长度。

代码如下：

public class LongestIncresing2 {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return 0;
        }
        //初始化最长递增子序列的长度为1，因为只要数组不为空，最小递增子序列可以为单个元素，即长度为1
        int max = 1;
        //初始化代表从每个以nums[index]结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        for (int index = 0; index < nums.length; index++) {
            dp[index] = 1;
            for (int dpIndex = 0; dpIndex < index; dpIndex++) {
                //如果index处的数大于它前边位置为dpIndex的数，就将dp[index]和dp[dpIndex]+1中较大的数更新为index处的dp[index]
                if (nums[dpIndex] <= nums[index]) {
                    dp[index] = Math.max(dp[index], dp[dpIndex] + 1);
                    //同时将最大值也更新
                    max = Math.max(dp[index], max);
                }
            }
        }

        return max;
    }


    public static void main(String[] args) {
        LongestIncresing2 li = new LongestIncresing2();
        int[] arr = {10,9,2,5,3,7,101,18};

        System.out.println(li.lengthOfLIS(arr));
    }
}