实现功能:产生一个随机整型数组(默认长度为10),并找出数组的最长递增子序列。
采用动态规划思想,参考资料:最长递增子序列详解。
代码实现:
package homework.seven; public class LongestIncreasingSubsequence { /** * @param n 指定数组长度 * @param maxValue 指定随机数组元素的最大值 * @return 返回随机int[n] */ public int[] creatRandomArray(int n,int maxValue){ int[] randomArray = new int[n]; for(int i=0;i<n;i++){ randomArray[i] = (int)(Math.random()*maxValue); } //输出生成的随机数组 for(int i:randomArray){ System.out.print(i+"\t"); } System.out.println(); return randomArray; } /** * @param array 需执行寻找最长子序列的数组 * @return 最长子序列数组 */ public int[] list(int array[]) { int length = array.length; int[] currentMaxLenght = new int[length]; int i, j, k, max,maxLength; //以当前元素作为最大值的递增子序列 int[] maxElements = new int[length]; for(i = 0; i < length; ++i) { currentMaxLenght[i] = 1; maxElements[i] = i; } for(i = 1, max = 1, k = 0; i < length; ++i) { //找到以array[i]为最大元素的最长递增子序列 for(j = 0; j < i; ++j) { //递增(亦可递减>) if(array[j] < array[i] && currentMaxLenght[j] + 1> currentMaxLenght[i]) { currentMaxLenght[i] = currentMaxLenght[j] + 1; maxElements[i] = j; //当前最长递增子序列的长度 if(max < currentMaxLenght[i]) { max = currentMaxLenght[i]; k = i; } } } } //输出以当前元素作为最大元素的最长递增序列长度 for(int q: currentMaxLenght){ System.out.print(q+"\t"); } System.out.println(); maxLength = getMaxValueOfArray(currentMaxLenght); int[] maxValue = new int[maxLength]; i = max - 1; while(maxElements[k] != k) { maxValue[i--] = array[k]; k = maxElements[k]; } maxValue[i] = array[k]; return maxValue; } /** * @param array 需找出最大元素的整型数组 * @return 数组的最大元素值 */ public int getMaxValueOfArray(int[] array){ int value=0,length=array.length; for(int n=0;n<length;n++){ value = array[n]>value?array[n]:value; } return value; } public static void main(String[] args) { LongestIncreasingSubsequence aa = new LongestIncreasingSubsequence(); System.err.println("①生成的随机数组:"); System.err.println("②以当前元素作为最大元素的最长递增序列长度:"); System.err.println("③随机数组的最长递增子序列:\n"); int[] array = aa.creatRandomArray(10, 100); int[] value = aa.list(array); for(int i: value){ System.out.print(i+"\t"); } } }
测试结果: