1. 获得一个整形数组中的最长单调递增子串，并将其打印出来。
   
2. 假设源数据数组为arr，长度为n，用数组mem[n]来记录以0=<i<n下表为结尾元素的递增子串的个数,path[][]来记录以0=<i<n为下表元素的递增子串的各数据值。
   
3. 根据算法    mem0]=1, mem[i] = max{mem[k]}+1 (其中   0=<k<i,arr[k]<arr[i] )
   
4. 
   
5. 
   
6. public class GetMaxSubInt
   
7. {
   
8.         public static void main(String[] args)
   
9.         {
   
10.                 int[] a = {1,4,3,6,5,9};
    
11.                 MaxSubOrder(a);
    
12.         }
    
13.        
    
14.         public static void MaxSubOrder(int[] arr)
    
15.         {
    
16.                 int n = arr.length;                      //数据个数
    
17.                 int[] mem = new int[n];                  //急速每个递增子串的数据个数
    
18.                 int[][] path = new int[n][n+1];         //记录最长子串的值，其中path[i][n]用来记录以i未下表元素结尾的递增子串的数据个数
    
19.                 int i=0,j=0,k=0;               
    
20.                 int count = 0;                                //计数器
    
21.                 for(i=0,mem[0]=1; i<n; i++)
    
22.                 {
    
23.                         path[i] = new int[n+1];
    
24.                         count = 0;
    
25.                         for(j=0,k=0; j<i; j++)
    
26.                         {
    
27.                                 if((arr[j]<=arr[i]) && (k<mem[j]))    // 满足  0=<j<i arr[j]<arr[i] && 获得mem[i]
    
28.                                 {
    
29.                                         k = mem[j];
    
30.                                         path[i][count++] = arr[j];
    
31.                                 }
    
32.                         }
    
33.                         mem[i] = k+1;
    
34.                         path[i][count++] = arr[i];
    
35.                         path[i][n] = count;
    
36.                        
    
37.                 }
    
38.                
    
39.                 //获取mem[]中的最大值，即为最长递增子串值
    
40. 
    
41.                 for(i=0,k=0; i<mem.length; i++)
    
42.                 {
    
43.                         if(mem[i] > k)
    
44.                         {
    
45.                                 k = mem[i];
    
46.                                 j = i;
    
47.                         }
    
48.                 }
    
49.                
    
50.                 //输出最长递增子串
    
51.                 for(i=0; i<path[j][n]; i++)
    
52.                 {
    
53.                         System.out.print(path[j][i]+"  ");
    
54.                 }
    
55.         }
    
56. }
    
57. 
    
58. 算法所用时间为O(n*n)。

复制代码

值得学习ing!