求最长递增子序列~ - 编程论坛

#2

九转星河2018-03-18 15:22

问题是难度居然是基础题,我也是醉了,或者普通算法也能达到目的,有大神能给出一个可行能够AC的算法就可以了

~

#3

李晨经纪人2018-03-18 16:35

稍微改了下

程序代码：

#include<stdio.h>
int main(void)
{
    int i,j,n,max,num=0,m=0;
    int count[100]={0};
    int a[100];
    scanf("%d",&n);
    for(i=0;i<n;++i)
        scanf("%d",&a[i]);

    for(i=0;i<n-1;++i)
        for(j=i+1;j<n;++j)
            if(a[j]>a[i])
                count[i]++;
    max=count[0];
    for(i=0;i<n;++i)
    {
        if(count[i]>max)
        {
            max=count[i];
            num=i;
        }
    }
    for(i=num+1;i<n-1;++i)
    {

        for(j=i+1;j<n;++j)
        {
            if(count[j]>=count[i])
            {
                max--;
                break;
            }
        }
    }

    if(max<=-1)
        printf("0\n");
    else
        printf("%d",max+1);
    return 0;
}

[此贴子已经被作者于2018-3-18 18:33编辑过]

#4

九转星河2018-03-18 16:53

回复 3楼李晨经纪人

好

我去看看情况,有消息和你说说,希望简单改下条件可以AC

~

#5

李晨经纪人2018-03-18 17:00

回复 4楼九转星河

ac是什么

#6

九转星河2018-03-18 17:30

以下是引用李晨经纪人在2018-3-18 17:00:16的发言：

ac是什么

ACM题目通过了叫AC
当然我是帮我的一个同学问的,我还要等他消息,有点无语

~

#7

ehszt2018-03-18 20:52

测试 8（n）8 7 13 17 5 2 3 1结果为0

#8

ehszt2018-03-18 20:53

下面程序能得出结果但说不上原因，有待验证
#include<stdio.h>
int main(void)
{
     int i,j,n,max,min,num=0,count1,count2;
     int count[100]={0};
     int a[100];
     scanf("%d",&n);
     for(i=0;i<n;++i)
         scanf("%d",&a[i]);
         int pre=0,end=n-1;
     while(pre<=end)
     {
         max=a[pre];count1=0;
         for(j=pre;j<=end;++j)
             if(a[j]>max)
             {
                 max=a[j];
                 count1++;
             }
         min=a[end];count2=0;
         for(j=end;j>=pre;--j)
             if(a[j]<min)
             {
                 min=a[j];
                 count2++;
             }
         count[pre]=(count1>count2)?count1:count2;
     pre++;end--;

     }
     max=count[0];
     for(i=0;i<n;i++)
     {
         if(max<count[i]){
             max=count[i];
         }
     }

         printf("%d",max+1);
     return 0;
}
算法就是从头到尾，然后从尾到头也许还有漏掉的

[此贴子已经被作者于2018-3-18 20:55编辑过]

#9

李晨经纪人2018-03-18 21:12

回复 7楼 ehszt

对的，后面出现比较小的数字时会出错。把最后的一串count[i]=0的元素删除

#10

李晨经纪人2018-03-18 21:14

回复 7楼 ehszt

这样就不会把多余的数减掉了

#11

九转星河2018-03-18 22:25

2楼代码输入
10
100 150 200 300
201 202 203 204
9 8

的时候输出结果为5
期望结果应该是7
PS:8楼也是~
2018-3-18 22:25更

~

[此贴子已经被作者于2018-3-18 22:27编辑过]

#12

lanke7112018-03-19 02:05

回复楼主九转星河

最近挺累的。回来也没时间写。找了个二分查找法。我去南阳理工OJ测试了一下。AC了。那题原本是N<=100000的序列长度，这里是50000的序列长度
不知道你这是哪里的OJ题。所以我改了一下数组长度。去掉了多组测试数据。其它均未改变。你试试看。
#include <stdio.h>
//#include <stdlib.h>

int LIS(int *array, int n);
int BiSearch(int *b, int len, int w);
int p[50009];
int B[50009];
int len;

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &p[i]);
    }
    len = 0;
    printf("%d\n", LIS(p, n));

    return 0;
}

int LIS(int *array, int n)
{
    len = 1;
    B[0] = array[0];
    int i, pos = 0;

    for (i = 1; i<n; ++i)
    {
        if (array[i] > B[len - 1]) //如果大于B中最大的元素，则直接插入到B数组末尾
        {
            B[len] = array[i];
            ++len;
        }
        else
        {
            pos = BiSearch(B, len, array[i]); //二分查找需要插入的位置
            B[pos] = array[i];
        }
    }

    return len;
}

//修改的二分查找算法，返回数组元素需要插入的位置。
int BiSearch(int *b, int len, int w)
{
    int left = 0, right = len - 1;
    int mid;
    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (b[mid] > w)
            right = mid - 1;
        else if (b[mid] < w)
            left = mid + 1;
        else    //找到了该元素，则直接返回
            return mid;
    }
    return left;//数组b中不存在该元素，则返回该元素应该插入的位置
}

#13

九转星河2018-03-19 07:57

回复 12楼 lanke711

学习了

这个方法的确挺巧妙的~应该可以了

~

然后发现了原来是用了路径覆盖思想,的确比我那个求连通分量要简单很多,当然我那个方法理论上可以输出最长路径的~
当然了,能AC就可以了

~

[此贴子已经被作者于2018-3-19 08:04编辑过]

#14

will丶2018-03-19 09:42

动态规划的题

程序代码：

#include <stdio.h>
const int N = 50000;

int Bin(int key, int* d, int low, int high)
{
    while(low<=high)
    {
        int mid = (low+high)>>1;
        if(key>d[mid] && key<=d[mid+1])
            return mid;
        else if(key>d[mid])
            low = mid+1;
        else
            high = mid-1;
    }
    return 0;
}

int LIS(int* a, int n, int* d)
{
    int i,j;
    d[1] = a[1];
    int len = 1;
    for(i = 2; i <= n; i++)
    {
        if(d[len]<a[i])
            j = ++len;
        else
            j = Bin(a[i],d,1,len) + 1;//二分法查找
        d[j] = a[i];
    }
    return len;
}

int main()
{
    int a[N];
    int d[N];
    int t;
    int p;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&p);
        for(int i = 1; i <= p; i++)
            scanf("%d",&a[i]);
        printf("%d\n",LIS(a,p,d));
    }
    return 0;
}

#15

ehszt2018-03-19 15:41

#include<stdio.h>

int LIS(int arr[1000], int n)
{
    int dp[100];
    for(int i=1; i<=n; ++i)
        dp[i] = 0;
    int ans;
    dp[1] = 1;
    for(int i=2; i<=n; ++i)
    {
        ans = dp[i];
        for(int j=1; j<i; ++j)
        {
            if(arr[i]>arr[j] && dp[j]>ans)
                ans = dp[j];
        }
        dp[i] = ans+1;
        //printf("dp[%d]=%d ",i,dp[i]);
    }
    ans = 0;
    for(int i=1; i<=n; ++i)
    {
        if(dp[i] > ans)
            ans = dp[i];
    }
    return ans;
}

int main()
  {
      int i,j,n,max,min,num=0;
      int count[100]={0};
      int a[100];
      scanf("%d",&n);
      for(i=1;i<=n;++i)
          scanf("%d",&a[i]);
      printf("\n%d",LIS(a,n));
      return 0;
  }

#16

九转星河2018-03-19 16:00

回复 15楼 ehszt

这个是常规算法,容易理解~
就是用常规算法进行查找来获取位置 ~
但如果要卡效率的话这算法复杂度o(n^2)有可能超时哦

~

#17

九转星河2018-03-19 18:59

重写了sbeach函数,实现形式参考了标准库函数bsearch,实现主体参考了12楼的代码(特别拜谢

),当然个人感觉14楼的二分法查找下标从1开始适用范围比较有局限性
这个函数感觉这个对于查找最近插入点有一定帮助的,可以参考一下

~

程序代码：

size_t BsearchReIndex( const void* key,const void* base,size_t num,size_t size,int (*compartor)( const void*,const void* ) )
{
   size_t low=0;
   size_t height=num-1;

   while (low<=height&&height!=-1)
   {
       const size_t mid=low+(height-low>>1);

     const int comp=compartor(key,( const char* )base+mid*size);

    if (comp<0)
        height=mid-1;
    else if (comp>0)
        low=mid+1;
    else
        return mid;
   }

   return low;
}

#18

九转星河2018-03-20 01:18

写了个输出路径的,感觉有点绕,看看就行了

~

程序代码：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>

#define FREE( p )    \
    do    \
    {    \
        free(p);    \
        p=NULL;    \
    }while (0)

typedef struct Data
{
    int data;    //保存数据
    size_t mark;    //上一个数据下标

}Data,*P_Data;

size_t _bsearch( const void*,const void*,size_t,size_t ,int (*)( const void*,const void* ));

int comp(const void* ,const void* );

void malFun( void**,size_t );
void input( const P_Data*,size_t );

void printData( const Data[],size_t );

unsigned fun( Data[],size_t );

int main( void )
{
    P_Data data=NULL;

    size_t len=0;

    if ( !scanf("%u",( unsigned* )&len))
        exit(EXIT_FAILURE);

    input(&data,len);

    printData(data,fun(data,len));

    FREE(data);

    return 0;
}

int comp(const void* p,const void* q)
{
    const int _p=*( const int* )p;
    const P_Data _q=( const P_Data )q;

    if (_p>_q->data)
        return 1;

    if (_p<_q->data)
        return -1;

    return 0;
}

size_t _bsearch( const void* key,const void* base,size_t num,size_t size,int (*compartor)( const void*,const void* ) )
{
   size_t low=0;
   size_t height=num-1;

   while (low<=height&&height!=-1)
   {
       const size_t mid=low+(height-low>>1);

     const int comp=compartor(key,( const char* )base+mid*size);

    if (comp<0)
        height=mid-1;
    else if (comp>0)
        low=mid+1;
    else
        return mid;
   }

   return low;
}

void malFun( void** data,size_t size )
{
    assert(data);

    *data=malloc(size);

    assert(*data);

    memset(*data,0,size);
}

void input( const P_Data* data,size_t len)
{
    const size_t size=len*sizeof (Data);
    size_t i;

    if (!len)
        exit(EXIT_FAILURE);

    malFun(( void** )data,size);

    for (i=0;i!=len;++i)
        if (!scanf("%d",&(*data)[i].data))
            exit(EXIT_FAILURE);
        else
            (*data)[i].mark=i;


}

unsigned fun( Data data[],size_t len )
{
    P_Data road=NULL;

    const size_t dataSize=len*sizeof (Data);
    const size_t roadSize=len*sizeof (Data);

    size_t pos=0;

    size_t i;
    size_t j=1;

    malFun(( void** )&road,roadSize);

    road[0].data=data[0].data;
    road[0].mark=0;

    for (i=0;i!=len;++i)
        data[i].mark=-1;

    for (i=1;i<len;++i)
    {
        if (data[i].data>road[j-1].data)
            pos=j++;
        else
            pos=_bsearch(&data[i].data,road,j,sizeof (Data),comp);

       if (pos)
            data[i].mark=road[pos-1].mark;

        road[pos].data=data[i].data;
        road[pos].mark=i;

    }

    pos=road[j-1].mark;

   FREE(road);

    return pos;
}

void printData( const Data data[],size_t mark )
{
    int* road=NULL;

    size_t step;
    size_t t_step;

    size_t t_mark=mark;

    for (step=0;mark!=-1;++step)
        mark=data[mark].mark;

    malFun(( void** )&road,step*sizeof (int));

    for (t_step=step-1,mark=t_mark;mark!=-1;--t_step)
    {
        road[t_step]=data[mark].data;
        mark=data[mark].mark;
    }

     printf("\n最长子序列长度为%u,具体路径为:\n",( unsigned )step);
    while (++t_step!=step)
        printf("%-8d",road[t_step]);

    puts("");
    FREE(road);
}

[此贴子已经被作者于2018-3-20 08:28编辑过]

#19

ehszt2018-03-20 10:41

#include<stdio.h>
int dp[100];
int LIS(int arr[1000], int n)
{

    for(int i=1; i<=n; ++i)
        dp[i] = 0;
    int ans;
    dp[1] = 1;
    for(int i=2; i<=n; ++i)
    {
        ans = dp[i];
        for(int j=1; j<i; ++j)
        {
            if(arr[i]>arr[j] && dp[j]>ans)
                ans = dp[j];
        }
        dp[i] = ans+1;
        //printf("dp[%d]=%d ",i,dp[i]);    //每个数都有一个dp值
    }
    ans = 0;
    for(int i=1; i<=n; ++i)
    {
        if(dp[i] > ans)
            ans = dp[i];
    }
    return ans;
}

void footprint(int m,int n,int a[]) //打印路径
{
    int b[m+1];
    int c=m;
    for(int i=n;i>0;i--)
    {
        if(dp[i]==c)
        {
            b[c]=a[i];
            c--;
        }
    }
    printf("\n");
    for(int i=1;i<=m;i++)
    {
        printf("%d ",b[i]);
    }
}

int main()
  {
      int i,j,n,max,min,num=0,m;
      int count[100]={0};
      int a[100];
      scanf("%d",&n);
      for(i=1;i<=n;++i)
          scanf("%d",&a[i]);
      printf("\n%d",m=LIS(a,n));
      footprint(m,n,a);
      return 0;
  }

[此贴子已经被作者于2018-3-20 10:47编辑过]

#20

九转星河2018-03-20 11:58

回复 19楼 ehszt

赶紧吃个瓜来缓冲一下

~

#21

lanke7112018-03-21 01:25

回复 18楼九转星河

看到你用了compartor
我这有个几行的。。。
#include<algorithm>
#define MAX 50100
int count,num[MAX];

手机码的累。有一些就不打了。下面是main函数的代码。
int n,*p;
count=1;
scanf("%d",&n);
scanf("%d",&num[0]);
for(int i=1;i!=n;i++)
{
   scanf("%d",&num[i]);
   p=lower_bound(num,num+count,num[i]);
   if(p-num==count) ++count;
   *p=num[i];
}
printf("%d\n",count);

#22

九转星河2018-03-21 01:49

回复 21楼 lanke711

好是好,其实num[i]那里输入直接改用一个临时变量t保存或者更容易理解,当然用num[i]可以节省一行代码,不过实际上把num[i]输入那里改成num[count]看上去形象一点

PS:我也习惯手机敲代码,当然可以理解的,而且还成习惯了

~

[此贴子已经被作者于2018-3-21 01:55编辑过]