当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

编程之美-数组中最长递增子序列

发表于: 2012-08-09   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.Arrays; import java.util.Random; public class LongestAccendingSubSequence { /** * 编程之美 数组中最长递增子序列 * 书上的解法容易理解 * 另一方法书上没有提到的是,可以将数组排序(由小到大)得到新的数组, * 然后求排序后的数组与原数
import java.util.Arrays;
import java.util.Random;

public class LongestAccendingSubSequence {

	/**
	 * 编程之美 数组中最长递增子序列 
	 * 书上的解法容易理解
	 * 另一方法书上没有提到的是,可以将数组排序(由小到大)得到新的数组,
	 * 然后求排序后的数组与原数组的最长公共子序列
	 * 最长公共子序列可用动态规则求解,见http://bylijinnan.iteye.com/blog/1450435
	 * 最后,可以扩展一下:求最长递增子序列的长度的同时,求出这个子序列
	 */
	
	private static final int MAX_NUM = 10;
	private static int[] source = new int[2 * MAX_NUM];	//source存放-10~10这20个元素
	static {
		int len = 2 * MAX_NUM;
		for (int i = 0; i < len; i++) {
			source[i] = i - MAX_NUM;
		}
	}

	public static void main(String[] args) throws Exception {
		// int[] a = { 1, -1, 2, -3, 4, -5, 6, -7 };
		int i = 0;
		while (i++ < 30) {	//测试30次
			int[] a = generateArray(5); // 在source数组里面随机选取5个不同元素
			System.out.println(Arrays.toString(a));
			int length = lisA(a);
			System.out.println(length);
			int length2 = lisB(a);
			System.out.println(length2);
			if (length != length2) {
				throw new Exception("error");
			}
		}
	}
	
	public static int lisA(int[] a) {
		if (a == null || a.length == 0) {
			return -1;
		}
		int result = 0;
		int len = a.length;
		int[] LIS = new int[len];
		for (int i = 0; i < len; i++) {
			LIS[i] = 1;
			for (int j = 0; j <= i; j++) {
				if (a[j] < a[i] && (LIS[j] + 1) > LIS[i]) {
					LIS[i] = LIS[j] + 1;
				}
			}
		}
		for (int i = 0; i < len; i++) { // 找出LIS[i]的最大值
			if (LIS[i] > result) {
				result = LIS[i];
			}
		}
//		System.out.println(Arrays.toString(LIS));
		return result;
	}

	public static int lisB(int[] a) {
		if (a == null || a.length == 0) {
			return -1;
		}

		int len = a.length;
		int[] minLast = new int[len + 1]; // minLast[i]表示长度为i的递增子序列里(长度相等的递增子序列可能有多个),各个子序列最后一个元素的集合里面的最小值
		minLast[1] = a[0];
		minLast[0] = Integer.MIN_VALUE;
		int[] LIS = new int[len];
		for (int i = 0; i < len; i++) {
			LIS[i] = 1;
		}
		int maxLIS = 1; // 递增子序列的最长长度
		for (int i = 1; i < len; i++) {
			int j = 0;
			//从后往前找。另外,对于i<j,总有minLast[i]<minLast[j],因此minLast是个有序的递增数组。可用二分查找加快速度
			//书上说可以改成for (j = LIS[i-1]; j >= 1; j--) 我认为是不对的,因为maxLIS不一定等于LIS[i-1],且对于m<=n,LIS[m]<=LIS[n]不一定成立
			for (j = maxLIS; j >= 1; j--) {	
				if (a[i] > minLast[j]) { 
					LIS[i] = j + 1;
					break;
				} 
			}
			if (LIS[i] > maxLIS) {
				maxLIS = LIS[i];
				minLast[LIS[i]] = a[i];
			} else if (minLast[j] < a[i] && a[i] < minLast[j + 1]) {
				minLast[j + 1] = a[i];
			}
		}
//		System.out.println(Arrays.toString(LIS));
		return maxLIS;
	}
	
	private static int[] generateArray(int length) {
		assert length > 0;
		int[] a = new int[length];
		Random r = new Random();
		int len = source.length;
		int[] copyOfSource = new int[len];
		System.arraycopy(source, 0, copyOfSource, 0, len);
		for (int i = 0; i < length; i++) {
			int k = r.nextInt(len);
			a[i] = copyOfSource[k];
			copyOfSource[k] = copyOfSource[len - 1];
			len--;
		}
		return a;
	}
	
}

编程之美-数组中最长递增子序列

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
问题 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如
概述 最长递增子序列(Longest Increasing Subsequence)长度有很多种解决方法,这里介绍两种,一种是
问题 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如
最长递增子序列dp 动态规划 (DP) 之 最长递增子序列(Longest Increase Subsequence) 原文:http://b
本文内容框架: §1 连续子数组最大和 基本方法、分治策略求解、动态规划求解 §2 最长递增子序列 排
问题描述 最长递增子序列也称 “最长上升子序列”,简称LIS ( longest increasing subsequence)。设
非常经典的几个算法题,下面这篇文章写的很好。直接转来了。有时候发觉一口气要手写出这些算法还是
一、本文内容 最长递增子序列的两种动态规划算法实现,O(n^2)及O(nlogn). 二、问题描述 最长递增子
Bridging signals Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Oth
参考链接: a.http://www.programfan.com/blog/article.asp?id=13086 b.http://blog.csdn.net/hhygc
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号