非动态规划---LIS

题目：一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。(见动态规划---LIS)

 1 /*
 2 题目：一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。
 3 */
 4 #include <stdio.h>
 5 
 6 unsigned max_len( int [] , size_t );
 7 size_t b_point( int [] , size_t );
 8 int max(size_t , size_t );
 9 
10 int main( void )
11 {
12    
13   int arr[] = { 4 , 5 , 3 , 3 , 3 , 3 , 6 , 5 , 1 , 2 };
14 
15   printf("%u
" , max_len( arr , sizeof arr / sizeof arr[0] ) ); 
16 
17   return 0;
18 }
19 
20 unsigned max_len( int a[] , size_t n )
21 {
22    if ( n <= 1u )
23       return n ; 
24    
25    size_t m = b_point ( a , n ) ;
26    
27    return max( m , max_len ( a + m , n - m ) ) ;  
28    
29 }
30 
31 size_t b_point ( int a[] , size_t n )
32 {
33    size_t i ;
34    
35    for ( i = 1u ; i < n ; i++ )
36       if ( a[i-1] > a[i])
37          return i - 0u ;
38 
39    return i - 0u ;
40 }
41 
42 int max( size_t n1 , size_t n2 )
43 {
44    if ( n1 > n2 )
45       return n1;
46 
47    return n2;
48 }

 1 /*
 2 题目：一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。
 3 */
 4 #include <stdio.h>
 5 
 6 unsigned max_len( int [] , size_t );
 7 size_t b_point( int [] , size_t );
 8 
 9 int main( void )
10 {
11   int arr[] = { 4 , 5 , 3 , 3 , 3 , 3 , 6 , 5 , 1 , 2 };
12 
13   printf("%u
" , max_len( arr , sizeof arr / sizeof arr[0] ) ); 
14 
15   return 0;
16 }
17 
18 unsigned max_len( int a[] , size_t n )
19 {
20    size_t len = 0u ; 
21    while ( n > 0u )
22    {
23       size_t mid = b_point( a , n );
24       
25       if ( mid > len )
26          len = mid ;
27          
28       a += mid ;
29       n -= mid ;
30    } 
31    return len ;
32 }
33 
34 size_t b_point ( int a[] , size_t n )
35 {
36    size_t i ;
37    
38    for ( i = 1u ; i < n ; i++ )
39       if ( a[i-1] > a[i])
40          return i - 0u ;
41 
42    return i - 0u ;
43 }

非 动态规划---LIS

非动态规划---LIS