public int LIS(int[] array) {
    int[] dp = new int[array.length];
    
	int[] pre = new int[array.length];		// 用于求出具体的递增序列
	for (int i = 0; i < array.length; i++) 
		pre[i] = i;
	
	dp[0] = 1;

	
    int max = 0;
    for (int i = 1; i < array.length; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (array[j] < array[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
				if (dp[j] + 1 > dp[i])
					pre[i] = j;
			}
        }
        
        max = Math.max(dp[i], max);
    }
	
	
	int maxIndex = 0;
	for (int i = 0; i < array.length; i++) {
		if (dp[i] == max)
			maxIndex = i;
	}
	
	List<Integer> list = new ArrayList<>();
	int index = maxIndex;
	while(index != pre[index]) {
		list.add(array[index]);
		index = pre[index];
	}
	
    
	
	
    return max;
}