回 帖 发 新 帖 刷新版面

主题:第31次比赛第1题_题目

一系列整数 (a[1],a[2],a[3], ..., a[n]),如果数列(a[i],a[i+1],a[i+2]…… a[k])满足a[i]<a[i+1]<a[i+2]<…… <a[k]则称为递增数列。
如果(a[i],a[i+1],a[i+2]…… a[k])中所有元素都属于数列(a[1],a[2],a[3], ..., a[n]),则称数列(a[i],a[i+1],a[i+2]…… a[k])为数列
(a[1],a[2],a[3], ..., a[n])的子数列。
----------------------------------
问题:
   给一长度为len的整型数列(array[1],array[2],array[3], ..., array[len]),求该数列中最长的子递增数列的长度.
   其中,-1000<=a[i]<=1000,1<=len<=1000
----------------------------------
函数接口:
       int maxclarray(int *array,int len);
       接口说明:
               array----整型数列的首地址
               len------整型数列的长度
               返回值---最长的子递增数列的长度
----------------------------------
如:
  a[]={1,-2,1,2,1},len=5; 返回3

  a[]={1,-2,-11,-2,1},len=5; 返回3

  a[]={1,-2,-3,-4,-5,-6,-7},len=7; 返回1

  a[]={1},len=1; 返回1

-----------------------------------

有什么疑问,可以在"关于31次比赛第1题"贴提出

------------------------------------

最后,祝大家周末愉快!!!1

回复列表 (共20个回复)

11 楼

int maxclarray(int *a,int len)
{
    int max=0;
    int start=0;
    for(int i=0;i<len-1;++i)
    {
        if(len-i<max)
            return max;
        if(a[i+1]>a[i])
            continue;
        else if(i-start>max)
        {
            max=i-start+1;
            start=i;
        }
        else
            start=i+1;
    }
    if(len-start>max)
        return len-start;
    return max;
}

12 楼

int sq(int *array,int &b,int len)
{
    int i=1;
    while (array[b++]<array[b+1]) 
        if (b<len-1) 
            i++;
        else 
        {
            i++;
            break;
        }
    return i;
}

int maxclarray(int *array,int len)
{
    int max(0),t(0),last(0);
    if (len<=1) return len; 
    while ((t+max)<len)
    {
        last=sq(array,t,len);
        max=max>last?max:last;
    }
    return max;
}

13 楼

int maxclarray(int *array, int len)
{
   if ( len <= 1 )
      return len == 1 ? 1 : 0;
   int count = 0;
   int maxcount = 0;
   for ( int i = 1; i < len; i++ )
      if ( array[i] > array[i-1] )
            count++;
      else
      {
         if ( count > maxcount )
            maxcount = count;
         count = 0;
      }
   return maxcount > count ? ++maxcount : ++count;
}

14 楼


先贡献一个。 这个题目是多久出一次。我感觉好像更新挺快的。05年寒假的时候好象是第一期吧。 
这个比较直接。
#include <iostream.h>
int maxclarray(int *array,int len);
void main()
{
    int array[10]={0,1,2,6,9,46,48,71,75,3};
    int m;
    cout<<maxclarray(array,m)<<endl;
}
int maxclarray(int *array,int len)
{
    int Low=0; // 数组的下标
    int High=9; //  数组的上标=数组的长度
    int Num=0;  //记数器
    while(Low<High)
    {
        int m1=1;  //控制数组中为递增数列的最大值
        while(array[Low]<array[Low+1] && Low<High)
        {
            Low++;
            ++m1;
        }
        if(Low < High)
            Low++; // 内部防止溢出
        if(Num<m1)  // 判断其中最大的一个值
        {
            Num=m1;
        }
    }
    return Num;
}

15 楼

#include <iostream>
using namespace std;
int maxclarray(int *array,int len);
int main()
{
    int *a,*b,k=1;
    a=new int;
    b=a;
    cout<<"输入数列数字(以空格分隔,回车结束): ";
    cin>>*a++;
    while(cin.get()!='\n')
    {
        cin>>*a++;
        k++;
    }
    if(k>1000){
        cout<<"输入的数列项过多!";
        return 1;
    }
    cout<<"数列总长度为: "<<k<<"\n最长的数列长度为: "<<maxclarray(b,k)<<endl;
    return 0;
}

int maxclarray(int *array,int len)
{
    int count=1,max=0,temp;
    //count计数器,max最大数列长度
    while(len--){
        temp=*array++;
        if(temp<*array)
            count++;
        else if(count>max){
            max=count;
            count=1;
        }
    }
    if(--count>max)max=count;
    return max;
}

//这题编得蛮快的,不知道是简单还是水品不够,如果编得不好,忘鉴谅!

16 楼

不做了 做也除非抄那两位大虾的 别无良策

17 楼

在贡献一个折半的方法

// 本算法是折半查找递增数列;
// 由于时间仓促有些东西封装的不是太好.
#include <iostream.h>
int Num;
int maxclarray(int *array,int len);
int ABC(int Low,int High,int *array,int Mid1,int Mid2);
void main()
{
    int array[10]={10,11,94,193,292,391,491,591,675,773};
    int m;
    cout<<maxclarray(array,m)<<endl;
}
int maxclarray(int *array,int len)
{
    int Low=0;     // 数组中的最小下标
    int High=9;    // 数组中的最大下标
    int Mid1,Mid2;
    ABC(Low,High,array,Mid1,Mid2);
    return Num;
    //cout<<MaxNum<<endl;
}
int ABC(int Low,int High,int *array,int Mid1,int Mid2)
{
    int m=1;
    if(Low<High)
    {
        Mid1=Mid2=(Low+High)/2;
        while(array[Mid1]<array[Mid1+1] && Mid1<High) // 折半后向上查找
        {
            Mid1++;
            m++;
        }
        while(array[Mid2]>array[Mid2-1] && Mid2>Low)  // 折半后想下查找
        {
            Mid2--;
            m++;
        }
        if(Num<m)
        {
            Num=m;
        }
        High=Mid2;
        ABC(Low,High,array,Mid1,Mid2); // 递归传递向下继续分
        Low=Mid1;
        ABC(Low,High,array,Mid1,Mid2); // 递归传递向上继续分
    }
    return Num;
}

18 楼

#include<stdio.h>

int maxclarry(int *array,int len)
{
  int temp=0;
  int count=1;
  int i;
  for(i=0;i<len-1;i++)
  {
    if(array[i]<array[i+1])count++;
    else if(temp<count){temp=count;count=1;}
    else count=1;
  }
  return (count>temp)?count:temp;
}

main()
{
   int len=6;
   int a[6]={6,5,4,3,2,1};
   int count;
   count=maxclarry(a,len);
   printf("%d",count);
}

19 楼

----------------------------------
简单实现函数:
       int maxclarray(int *array,int len);
       接口说明:
               array----整型数列的首地址
               len------整型数列的长度
               返回值---最长的子递增数列的长度
----------------------------------
int maxclarray(int *array,int len)
{
    int max=0;//待返回值
    for(int i=0;i<len;i++)
    {
        if((len-i)<=max)//剩余的数组长度小于max,跳出循环
            break;

        int m=1,k=i;
        for(int j=i;j<len;j++)
        {
            if(array[k]<array[j])//寻找子递增数列
            {
                m++;
                k=j;
            }
            else
                continue;
        }
        if(m>max)
            max=m;
    }
    return max;
}

20 楼

#include "stdio.h"
#include "stdlib.h"

int maxclarry(int *arry,int len)
{
    int count=1,record=1;
    for(int i=1;i<len;i++){
        if(arry[i]>arry[i-1]) count++;
        else if(count>record) {record=count;count=1;}
        else count=1;
    }
    if(record>count) return record;
    return count;
}

int main()
{
    int arry[20]={1,2,3,4,2,5,6,7,8,9,3,4,7,9,12,13,14,19,2,4};
    printf("%d\n",maxclarry(arry,20));
    system("Pause");
    return 0;
}
VS2005 下通过

我来回复

您尚未登录,请登录后再回复。点此登录或注册