Longest Increasing Subsequence(最長増分子シーケンス)

package cn.xidian.edu.LIS;

import java.util.Arrays;

public class Lis {

	public static void main(String[] args) {
		int nums[] = {2, 1, 5, 3, 6, 4, 8, 9, 7};
		System.out.println(solve2(nums));
	}
	private static int solve1(int[] nums) {
		//o(n^2)
		int[] LIS = new int[nums.length];
		for (int i = 0; i < nums.length; i++) {
			LIS[i] = 1;
			for (int j = 0; j < i; j++) {
				if (nums[i]>nums[j] && LIS[j]+1>LIS[i]) {
					LIS[i] = LIS[j]+1;
				}
			}
		}
		Arrays.sort(LIS);
		return LIS[LIS.length-1];
	}
	private static int solve2(int[] nums) {
		//o(n*logn)
		int[] LIS = new int[nums.length+1];
		LIS[1] = nums[0];
		int len = 1;
		for (int i = 1; i < nums.length; i++) {
			int pos = findPos(LIS, 1, len, nums[i]);
			LIS[pos] = nums[i];
			if (len < pos) {
				len = pos;
			}
		}
		return len;
	}
	private static int findPos(int[] lIS, int s, int e, int key) {
		if (key >= lIS[e]) {
			return e+1;
		}
		while (s <= e) {
			int mid = s+(e-s)/2;
			if (lIS[mid] > key) {
				e = mid-1;
			} else if (lIS[mid] < key){
				s = mid+1;
			} else {
				return mid;
			}
		}
		return s;
	}
}