动态规划算法学习十例之九

最长单调递增子序列的长度问题
  所谓子序列，就是在原序列里删掉若干个元素后剩下的序列，以字符串"abcdefg"为例子，去掉bde得到子序列"acfg"，。现在的问题是，给你一个数字序列，你要求出它最长的单调递增子序列的长度（LIS）。

  设给定序列为 array[]，大小为 n， 最长单调子序列必定以序列array[]中的某一个元素结尾，这是废话。

    设lis[i]为以array[i]结尾的最长单调子序列的长度，那么array[]的LIS的长度就是
max{lis[i]} (0<=i<n)

显然此问题具有最优子结构性质:
    lis[0]=1;
    lis[i+1]=max{1,lis[k]+1} (array[i+1]>array[k], k <= i)

即如果array[i+1]大于array[k],那么第i+1个元素可以接在lis[k]长的子序列后面构成一个更长的子序列。于此同时array[i+1]本身至少可以构成一个长度为1的子序列。

import java.util.Scanner;
public class TestLIS{
  private  int n;
  private int array[];
  private int lis[];

   public TestLIS(int n,int[] array){
      this.n=n;
      this.array=array;
      lis=new int[n];
   }

   public static void main(String[] args) { 
     
        Scanner in=new Scanner(System.in); 
        
           int n=in.nextInt(); 
           int[] array=new int[n]; 
           for(int i=0;i<n;i++){
                array[i]=in.nextInt(); 
           }  
         
          TestLIS tl=new TestLIS(n,array);
          int maxl=tl.lis();
          
          System.out.println("最长单调递增子序列长度："+maxl); 
          System.out.println();
          System.out.println("最长单调递增子序列构成");
          int k=tl.max();
          tl.print(k);
          System.out.println();
      
       
   }
  //求数组最长递增子序列
  public  int lis()
  {
	for(int i =0;i< n;i++)
	{
		lis[i]=1;
		for(int j=0;j< i;j++)
		{
			if(array[j]< array[i]&&(lis[j]+1>lis[i]))
			  lis[i]=lis[j]+1;
                       
                
		}
               
	}
	int max=0;
	for(int k=0;k< lis.length;k++)
	{
   		if(lis[k]>max)
		max=lis[k];
	}
  	return max;
   }

 //求数组中最大值下标  
    private int max()  
    {  
        int max = lis[0];  
        int k = 0;  
        for (int i = 0; i < lis.length; i++)  
        {  
            if (max < lis[i])  
            {  
                max = lis[i];  
                k = i;  
            }  
        }  
        return k;  
    }  

     //输出   
    public void print(int k)  
    {      
        for (int i = k - 1; i >= 0; i--)  
        {  
            if (lis[k] == lis[i] + 1 && array[i] <= array[k])  
            {  
                print(i);  
                break;  
            }  
        }  
        System.out.print(array[k] + " ");  
    }  

 }

运行：
5
1 10 4 9 7
最长单调递增子序列长度：3

最长单调递增子序列构成
1 4 9

下载：

动态规划算法学习十例之九