算法分析與設計-11-最長遞增子序列的動态規劃算法

最長遞增子序列的動态規劃算法

#include<stdio.h>
#define NUM 100
int a[NUM];
int LIS(int n)
{
         int b[NUM]={0};
         int i,j;
         b[1]=1;
         int max=0;
         for(i=2;i<=n;i++){
                   int k=0;
                   for(j=1;j<i;j++){
                                     if(a[j]<=a[i]&&k<b[j])k=b[j];
                            b[i]=k+1;
                            if(max<b[i])max=b[i];
                   }
         }
         return max;
}
int main(){
         int n,m,lis;
         printf("請輸入元素個數n:\n");
         scanf("%d",&n);
         printf("請輸入各元素的值:\n");
         for(int i=1;i<=n;i++){
           scanf("%d",&m);
           a[i]=m;       
         }
          printf("輸出最大個數：\n");
     lis=LIS(n);
     printf("%d",lis);
}
           

運作效果：