动态规划之最长单调递增子序列

问题描述:
找出由n个数组成的序列的最长单调递增子序列

解法一：

原序列记为X,对n个数递增排序,构造一个新序列Y, 对X,Y求其最长公共子序列即可.

/*
 * description: 最长单调递增子序列
 * 问题描述:
 * 找出由n个数组成的序列的最长单调递增子序列
 * 算法设计：
 * 解法一：
 * 原序列记为X,对n个数递增排序,构造一个新序列Y, 对X,Y求其最长公共子序列即可.
 * 
 * auther:cm
 * date:2010/11/17
 */
import java.util.LinkedList;
import java.util.List;
public class LISLength 
{
	private int[] arrX;
	private int[] arrY;
	private int[][] c;

	public LISLength(int[] arr)
	{
		arrX = new int[arr.length + 1];
		arrY = new int[arr.length + 1];
		System.arraycopy(arr,0,arrX,1,arr.length);
		System.arraycopy(arr,0,arrY,1,arr.length);
		selectSort(arrY, arrY.length - 1);
		lisLength();
	}

	//计算最长公共子序列
	public void lisLength()
	{
		c = new int[arrX.length][arrY.length];

		for (int i = 1; i < arrX.length; i++)
		{
			for (int j = 1; j < arrY.length; j++)
			{
				if (arrX[i] == arrY[j])
				{
					c[i][j] = c[i-1][j-1] + 1;
				}
				else
				{
					c[i][j] = max(c[i-1][j], c[i][j-1]);
				}
			}
		}
	}

	//返回最长单调递增子序列
	public List<Integer> getLIS()
	{
		LinkedList<Integer> list = new LinkedList<Integer>();
		int i = arrX.length - 1;
		int j = arrY.length - 1;
		while (i >= 1 && j >= 1)
		{
			if (arrX[i] == arrY[j])
			{
				list.addFirst(Integer.valueOf(arrX[i]));
				i--;
				j--;
			}
			else
			{
				if (c[i-1][j] > c[i][j-1])
				{
					i--;
				}
				else
				{
					j--;
				}
			}
		}
		return list;
	}

	private int max(int m, int n)
	{
		return m > n ? m : n;
	}

	//选择排序,0号空间不用
	private void selectSort(int[] a, int n)
	{
		for (int i = 1; i < n; i++)
		{
			int k = i;
			for (int j = i + 1; j <= n; j++)
			{
				if (a[k] > a[j])
				{
					k = j;
				}
			}
			if (k != i)
			{
				int temp = a[k];
				a[k] = a[i];
				a[i] = temp;
			}
		}
	}

	public static void main(String[] args) 
	{
		int[] arr = {4, 2, 3, 1, 8};
		//int[] arr = {8,9,10,2,3,4,5,6};
		LISLength lis = new LISLength(arr);
		List<Integer> a = lis.getLIS();
		for (Integer item: a)
		{
			System.out.print(item + " ");
		}
	}
}

序列X={4, 2, 3, 1, 8}

执行结果：

2 3 8

 

解法二：
1)用一个数组b[n]记录以a[i]结尾的最长单调递增子序列的长度;
2)序列的a的最长单调子序列的长度为max{b[i],0=<i<n};
3)b[i] = max{b[k],a[k]<=a[i]&&0=<k<i} + 1 ,b[0] = 1;

/*
 * description:最长单调递增子序列
 * 问题描述:
 * 找出由n个数组成的序列的最长单调递增子序列
 * 算法设计：
 * 解法二：
 * 1)用一个数组b[n]记录以a[i]结尾的最长单调递增子序列的长度;
 * 2)序列的a的最长单调子序列的长度为max{b[i],0=<i<n};
 * 3)b[i] = max{b[k],a[k]<=a[i]&&0=<k<i} + 1 ,b[0] = 1;
 * 
 * auther:cm
 * date:2010/11/17
 */
public class LIS
{
	private int[] a;
	private int[] b;

	public LIS(int[] a)
	{
		this.a = a;
		b = new int[a.length];
	}

	public void lis()
	{
		b[0] = 1;

		for (int i = 0; i < a.length; i++)
		{
			int k = 0;
			for (int j = 0; j < i; j++)
			{
				if (a[j] <= a[i] && k < b[j])
				{
					k = b[j];
				}
			}
			b[i] = k + 1;
		}
		int k = max(b);
                //输出结果
		print(k);
	}

	//求数组中最大值下标
	private int max(int[] b)
	{
		int max = b[0];
		int k = 0;
		for (int i = 0; i < b.length; i++)
		{
			if (max < b[i])
			{
				max = b[i];
				k = i;
			}
		}
		return k;
	}

	//输出
	public void print(int k)
	{
		for (int i = k - 1; i >= 0; i--)
		{
			if (b[k] == b[i] + 1 && a[i] <= a[k])
			{
				print(i);
				break;
			}
		}
		System.out.print(a[k] + " ");
	}

	public static void main(String[] args) 
	{
		int[] a = {4, 2, 3, 1, 8};
		LIS lis = new LIS(a);
		lis.lis();
	}
}

序列X={4, 2, 3, 1, 8}

执行结果：

2 3 8