【转】动态规划：最长递增子序列Longest Increasing Subsequence

转自：https://www.cnblogs.com/coffy/p/5878915.html

设f(i)表示L中以a _i 为末元素的最长递增子序列的长度。则有如下的递推方程：

这个递推方程的意思是，在求以a _i 为末元素的最长递增子序列时，找到所有序号在L前面且小于a _i 的元素a _j ，即j<i且a _j <a _i 。如果这样的元素存在，那么对所有a _j ,都有一个以a _j 为末元素的最长递增子序列，设其长度为f(j)，把其中最大的f(j)选出来，那么f(i)就等于最大的f(j)加上1，即以a _i 为末元素的最长递增子序列，等于以使f(j)最大的那个a _j 为末元素的递增子序列，再加上a _i ；如果这样的元素不存在，那么a _i 自身构成一个长度为1的以a _i 为末元素的递增子序列。

public void lis(float[] L)

  {

         int n = L.length;

         int[] f = new int[n];//用于存放f(i)值；

         f[0]=1;//以第a1为末元素的最长递增子序列长度为1；

         for(int i = 1;i<n;i++)//循环n-1次

         {

                f[i]=1;//f[i]的最小值为1；

                for(int j=0;j<i;j++)//循环i 次

                {

                       if(L[j]<L[i]&&f[j]+1>f[i])//f[j]+1>f[i]意思是以j结尾的递增序列加上元素i之后，整个递增序列变得更长了

                              f[i]=f[j]+1;//更新f[i]的值。//

                }

         }

        //f[i]的值是以L[i]为结尾的递增子序列的长度，需要求LIS，所以要取其中的最大值。

        return max(f);

  }