欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-02-24 23:49:58
...

转载自: https://blog.csdn.net/tterminator/article/details/50957527

一、问题描述

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

其它分析详见算法代码注释。

三、算法代码

  1. public static void maxAscLen(int [] arr){
  2. int n = arr.length;
  3. int [] lens = new int[n];//保存以每个元素i结尾的递增子序列长度
  4. int [][] lensArr = new int[n][n];//保存以每个元素i结尾的递增子序列
  5. for(int i = 0; i <= n - 1; i++){//初始化辅助空间
  6. lens[i] = 1;
  7. lensArr[i][0] = arr[i];
  8. }
  9. for(int i = 0; i <= n - 1; i++){
  10. int curMaxLen = 1;
  11. for(int j = i - 1; j >= 0; j--){//从后往前寻找
  12. if(arr[i] > arr[j] && lens[j] + 1 > curMaxLen){
  13. curMaxLen = lens[j] + 1;//更新以元素i结尾的最长递增子序列长度
  14. lens[i] = curMaxLen;
  15. for(int k = 0; k <= lens[j]; k++){//把以元素j结尾的最长递增子序列拷贝到以元素i结尾的最长递增子序列中
  16. lensArr[i][k] = lensArr[j][k];
  17. }
  18. lensArr[i][lens[i] - 1] = arr[i];
  19. }
  20. }
  21. }
  22. //寻找最大递增子序列长度的元素下标
  23. //这里只能找到第一个最长递增子序列的下标,例如本例中的最长子序列分别为{2,3,6,9},{2,3,6,7}
  24. //也即这里只能返回9的下标
  25. int index = 0;
  26. for(int i = 0; i <= n - 1; i++){
  27. if(lens[index] < lens[i]){
  28. index = i;
  29. }
  30. }
  31. //这里只能输出一个最长递增子序列
  32. System.out.println("最大递增子序列长度:" + lens[index]);
  33. System.out.print("最大递增子序列为:");
  34. for(int i = 0; i <= lens[index] - 1; i++){
  35. System.out.print(lensArr[index][i] + " ");
  36. }
  37. System.out.println();
  38. // return lens[index]; //可以返回最大最大递增子序列长度
  39. }
四、完整测试代码

  1. public class Solution {
  2. public static void main(String [] args){
  3. int [] randArr = new int[]{5,2,8,6,3,6,9,7};
  4. maxAscLen(randArr);
  5. }
  6. public static void maxAscLen(int [] arr){
  7. int n = arr.length;
  8. int [] lens = new int[n];//保存以每个元素i结尾的递增子序列长度
  9. int [][] lensArr = new int[n][n];//保存以每个元素i结尾的递增子序列
  10. for(int i = 0; i <= n - 1; i++){//初始化辅助空间
  11. lens[i] = 1;
  12. lensArr[i][0] = arr[i];
  13. }
  14. for(int i = 0; i <= n - 1; i++){
  15. int curMaxLen = 1;
  16. for(int j = i - 1; j >= 0; j--){//从后往前寻找
  17. if(arr[i] > arr[j] && lens[j] + 1 > curMaxLen){
  18. curMaxLen = lens[j] + 1;//更新以元素i结尾的最长递增子序列长度
  19. lens[i] = curMaxLen;
  20. for(int k = 0; k <= lens[j]; k++){//把以元素j结尾的最长递增子序列拷贝到以元素i结尾的最长递增子序列中
  21. lensArr[i][k] = lensArr[j][k];
  22. }
  23. lensArr[i][lens[i] - 1] = arr[i];
  24. }
  25. }
  26. }
  27. //寻找最大递增子序列长度的元素下标
  28. //这里只能找到第一个最长递增子序列的下标,例如本例中的最长子序列分别为{2,3,6,9},{2,3,6,7}
  29. //也即这里只能返回9的下标
  30. int index = 0;
  31. for(int i = 0; i <= n - 1; i++){
  32. if(lens[index] < lens[i]){
  33. index = i;
  34. }
  35. }
  36. //这里只能输出一个最长递增子序列
  37. System.out.println("最大递增子序列长度:" + lens[index]);
  38. System.out.print("最大递增子序列为:");
  39. for(int i = 0; i <= lens[index] - 1; i++){
  40. System.out.print(lensArr[index][i] + " ");
  41. }
  42. System.out.println();
  43. // return lens[index]; //可以返回最大最大递增子序列长度
  44. }
  45. }
五、运行结果

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