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

转载自： 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]

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

三、算法代码

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