主题:第31次比赛第1题_题目
天边蓝 [专家分:1810] 发布于 2006-06-16 20:06:00
一系列整数 (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 楼
fantasyzzz [专家分:0] 发布于 2006-06-17 13:33:00
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 楼
天国龙 [专家分:490] 发布于 2006-06-17 14:27:00
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 楼
wellerweldon [专家分:60] 发布于 2006-06-17 14:43:00
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 楼
xiaoyu8899 [专家分:10] 发布于 2006-06-17 16:14:00
先贡献一个。 这个题目是多久出一次。我感觉好像更新挺快的。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 楼
kcalf [专家分:0] 发布于 2006-06-17 17:15:00
#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 楼
yunzhou008 [专家分:410] 发布于 2006-06-17 19:31:00
不做了 做也除非抄那两位大虾的 别无良策
17 楼
xiaoyu8899 [专家分:10] 发布于 2006-06-17 23:07:00
在贡献一个折半的方法
// 本算法是折半查找递增数列;
// 由于时间仓促有些东西封装的不是太好.
#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 楼
Atins [专家分:20] 发布于 2006-06-18 01:59:00
#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 楼
wells1013 [专家分:0] 发布于 2006-06-18 02:46:00
----------------------------------
简单实现函数:
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 楼
jdxyw [专家分:230] 发布于 2006-06-18 10:20:00
#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 下通过
我来回复