Lintcode: Longest increasing subsequence (LIS)

Given a sequence of integers, find the longest increasing subsequence (LIS).You code should return the length of the LIS.Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

Understand the problem:
The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, length of LIS for { 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.

The problem is a classical computer science problem, LIS. Note that the problem asks to find out the subsequence, not substring. 

A DP Solution:
This is a sequence DP problem, so we define 

• dp[N], whereas dp[i] denotes the length of the LIS including the array element arr[i]. 
• Initial state: dp[i] = 1
• Transit function: for each j, where 0 <= j < i, if (A[i] >= A[j]), dp[i] = Math.max(dp[i], dp[j] + 1);
• Final state: result = 1, Math.max(result, dp[i]);

Code (Java):

public class Solution {
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        if (nums.length == 1) {
            return 1;
        }
        
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
        }
        
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] >= nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        int result = 1;
        for (int i = 0; i < nums.length; i++) {
            result = Math.max(dp[i], result);
        }
        
        return result;
    }
}

A wrong Solution:
Here is a wrong solution using the greedy idea. The basic idea is to use two loops, the outer loop i, starts from 0, and the inner loop starts from i + 1. For each inner loop, we scan through the array and compare the current value with the last one. The code is as follow:

Code (Java):

public class Solution {
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        if (nums.length == 1) {
            return 1;
        }
        
        int maxLen = 1;
        for (int i = 0; i < nums.length; i++) {
            int prev = nums[i];
            int len = 1;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] >= prev) {
                    len++;
                    prev = nums[j];
                }
            }
            maxLen = Math.max(maxLen, len);
        }
        
        return maxLen;
    }
}

The code cannot pass the test case :
[10,1,11,2,12,3,11]
where the correct result is 4 (1, 2, 3, 11), but the solution above will generate 3, (1, 11, 12). That is because when j is at 11, it will ignore 2 and generate the incorrect results.