动态规划算法之最长递增子序列有关问题

动态规划算法之最长递增子序列问题

一、问题描述

在数字序列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

动态规划算法之最长递增子序列有关问题

相关推荐