読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

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

Algorithm

リポジトリ
数列 (x_k)_{k=0, 1, \cdots n-1}が与えられたとき、 (x_k)からいくつかの項を脱落させた数列 (a'_k)_{k=0, 1, \cdots m-1 \leq n-1}を考える。
 i < j < mにおいて x'_i < x'_j が成立するとき (x'_k)を最長増加部分列(Longest Increasing Subsequence;LIS)という。

 O(n^2)

 DP_i:= x_iを最終要素とする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); }