软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 研发管理 -> 动态规划算法之最长递增子序列问题 -> 正文阅读
研发管理 最新文章
拉格朗日乘数
maven之可视化项目依赖(Visualizingdepend
mac效率工具
Atitit.css规范bem项目中CSS的组织和管理
git入门
Asimplemodelfordescribingbasicsourcesofp
Linux进程管理浅析
我的openwrt学习笔记(十九):linux便捷开
2、微控制器选择
Git使用手册:为Git仓库创建Submodule

[研发管理]动态规划算法之最长递增子序列问题

  2016-03-24 00:00:54

一、问题描述
在数字序列A中,按下标递增的顺序选出一个子序列B,如果选出的子序列B是严格递增的,则该子序列B称为原数字序列A的递增子序列。最长递增子序列问题就是找到原数字序列A中最长的递增子序列。例如数字序列5,2,8,6,3,6,9,7的一个最长递增子序列为2,3,6,9。
二、问题分析
动态规划函数为
L(i) = 1,                         i = 1或者不存在A[j] < A[i] (1 <= j < i)
      = max(L(j) + 1)        所有下标为1 <= j < i中,存在A[j] < A[i]
其它分析详见算法代码注释。
三、算法代码

public static void maxAscLen(int [] arr){
		int n = arr.length;
		int [] lens = new int[n];//保存以每个元素i结尾的递增子序列长度
		int [][] lensArr = new int[n][n];//保存以每个元素i结尾的递增子序列
		for(int i = 0; i <= n - 1; i++){//初始化辅助空间
			lens[i] = 1;
			lensArr[i][0] = arr[i];
		}
		
		for(int i = 0; i <= n - 1; i++){
			int curMaxLen = 1;
			for(int j = i - 1; j >= 0; j--){//从后往前寻找
				if(arr[i] > arr[j] && lens[j] + 1 > curMaxLen){
					curMaxLen = lens[j] + 1;//更新以元素i结尾的最长递增子序列长度
					lens[i] = curMaxLen;
					for(int k = 0; k <= lens[j]; k++){//把以元素j结尾的最长递增子序列拷贝到以元素i结尾的最长递增子序列中
						lensArr[i][k] = lensArr[j][k];
					}
					lensArr[i][lens[i] - 1] = arr[i];
				}
			}
		}
		
		//寻找最大递增子序列长度的元素下标
		//这里只能找到第一个最长递增子序列的下标,例如本例中的最长子序列分别为{2,3,6,9},{2,3,6,7}
		//也即这里只能返回9的下标
		int index = 0;
		for(int i = 0; i <= n - 1; i++){
			if(lens[index] < lens[i]){
				index = i;
			}
		}
		
		//这里只能输出一个最长递增子序列
		System.out.println("最大递增子序列长度:" + lens[index]);
		System.out.print("最大递增子序列为:");
		for(int i = 0; i <= lens[index] - 1; i++){
			System.out.print(lensArr[index][i] + " ");
		}
		System.out.println();
		
//		return lens[index]; //可以返回最大最大递增子序列长度
	}
四、完整测试代码

public class Solution {
	
	public static void main(String [] args){
		int [] randArr = new int[]{5,2,8,6,3,6,9,7};
		maxAscLen(randArr);
	}
	public static void maxAscLen(int [] arr){
		int n = arr.length;
		int [] lens = new int[n];//保存以每个元素i结尾的递增子序列长度
		int [][] lensArr = new int[n][n];//保存以每个元素i结尾的递增子序列
		for(int i = 0; i <= n - 1; i++){//初始化辅助空间
			lens[i] = 1;
			lensArr[i][0] = arr[i];
		}
		
		for(int i = 0; i <= n - 1; i++){
			int curMaxLen = 1;
			for(int j = i - 1; j >= 0; j--){//从后往前寻找
				if(arr[i] > arr[j] && lens[j] + 1 > curMaxLen){
					curMaxLen = lens[j] + 1;//更新以元素i结尾的最长递增子序列长度
					lens[i] = curMaxLen;
					for(int k = 0; k <= lens[j]; k++){//把以元素j结尾的最长递增子序列拷贝到以元素i结尾的最长递增子序列中
						lensArr[i][k] = lensArr[j][k];
					}
					lensArr[i][lens[i] - 1] = arr[i];
				}
			}
		}
		
		//寻找最大递增子序列长度的元素下标
		//这里只能找到第一个最长递增子序列的下标,例如本例中的最长子序列分别为{2,3,6,9},{2,3,6,7}
		//也即这里只能返回9的下标
		int index = 0;
		for(int i = 0; i <= n - 1; i++){
			if(lens[index] < lens[i]){
				index = i;
			}
		}
		
		//这里只能输出一个最长递增子序列
		System.out.println("最大递增子序列长度:" + lens[index]);
		System.out.print("最大递增子序列为:");
		for(int i = 0; i <= lens[index] - 1; i++){
			System.out.print(lensArr[index][i] + " ");
		}
		System.out.println();
		
//		return lens[index]; //可以返回最大最大递增子序列长度
	}
}
五、运行结果

最大递增子序列长度:4
最大递增子序列为:2 3 6 9 

上一篇文章      下一篇文章      查看所有文章
2016-03-24 00:00:46  
360图书馆 论文大全 母婴/育儿 软件开发资料 网页快照 文字转语音 购物精选 软件 美食菜谱 新闻中心 电影下载 小游戏 Chinese Culture
生肖星座解梦 三沣玩客 拍拍 视频 开发 Android开发 站长 古典小说 网文精选 搜图网 天下美图 中国文化英文 多播视频 装修知识库
2017-1-18 20:02:24
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --