最長増加部分列(longest increasing subsequence)

リポジトリ
数列が与えられたとき、からいくつかの項を脱落させた数列を考える。
においてが成立するときを最長増加部分列(Longest Increasing Subsequence;LIS)という。

版

を最終要素とするLIS長とすると
[tex: DP_i = \max \left \{ \begin{array}{lr} DP_j + 1 & (j

/**
 * Gets LIS(longest increasing subsequence) of x[begin, end)(O(n^2) n:= end - begin)
 * @param x	sequence
 * @param begin (inclusive) start index
 * @param end	(exclusive) end index
 * @return	LIS of x[begin, end)
 */
public static List<Integer> LIS(int[] x, int begin, int end){
	int n = end - begin;
	int[] DP = new int[n]; Arrays.fill(DP, 1);
	int[] prev = new int[n]; Arrays.fill(prev, -1);
	int lidx = 0;
	for(int i = 1; i < n; ++i){
		for(int j = 0; j < i; ++j)
			if(x[begin+j] < x[begin+i] && DP[i] < DP[j] + 1){ DP[i] = DP[j] + 1; prev[i] = j; }
		if(DP[lidx] < DP[i]) lidx = i;
	}
	LinkedList<Integer> lis = new LinkedList<Integer>();
	for(int i = lidx; i >= 0; i = prev[i]) lis.addFirst(x[begin+i]);
	return lis;
}
/**
 * Gets LIS(longest increasing subsequence) of x (O(n^2) n:= end - begin)<br>
 * @param x	sequence
 * @return	LIS of x
 */
public static List<Integer> LIS(int[] x){ return LIS(x, 0, x.length); }