Q:求数组中最长递增子序列的长度.

分析此问题，可以利用动态规划的思想来进行解决。对于第i个元素（0<i<N）个元素而言，以其结尾的递增子序列长度由前i-1个数组成的所有递增子序列长度来决定，于是该问题就分为了i-1个子问题。

maxLenIncr[i] = max{ maxLenIncr[k]+1, maxLenIncr[i]} if (a[i]>a[k] && k>=0&&k<i && i>0)

而当i=0时，maxLenIncr[0] =1. (maxLenIncr[i]表示以i结尾的最长递增子序列长度。)

实现的代码如下：

 1 #include <iostream.h>
 2 
 3 #define max(a,b) ((a)>(b)? (a):(b))
 4 
 5 int maxLenIncr(int* a, int len)
 6 
 7 {
 8     
 9     int* maxLenIncr=new int[len];
10     
11     int maxLen=1;
12     
13     
14     
15     /*Default value=1*/
16     
17     for(int i=0; i<len; i++)
18         
19     {
20         
21         maxLenIncr[i] = 1;
22         
23     }
24     
25     for( i=1; i<len; i++)
26         
27     {
28         
29         for(int k=0; k<i; k++)
30             
31         {
32             
33             if(a[i] > a[k])
34                 
35             {
36                 
37                 maxLenIncr[i]=max(maxLenIncr[k]+1, maxLenIncr[i]);
38                 
39                 if(maxLenIncr[i]>maxLen)
40                     
41                     maxLen=maxLenIncr[i];
42                 
43             }
44             
45         }
46         
47     }
48     
49     return maxLen;
50     
51 }

优质内容筛选与推荐>>
1、Samba服务部署
2、python学习笔记_week19
3、SQL查询
4、Android_scrollview
5、知物由学 |“网状世界”下，无处可逃的信息安全

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看