主题：第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个回复）
沙发
wksuper [专家分：660] 发布于 2006-06-16 21:02:00
int maxclarray(int *array,int len)
{
if(!array || len == 0) return 0;
int ret = 1, tmp = 1;
for(int i = 0; i < len; ++i)
{
if(i != len-1 && array[i] < array[i+1]) ++tmp;
else { ret = tmp > ret ? tmp : ret; tmp = 1;}
}
return ret;
}
板凳
fenix124 [专家分：70] 发布于 2006-06-16 21:33:00
//听说有O(nlogn)的算法,但是我不会,所以就写了个O(n^2)的
int maxclarray(int *array,int len)
{
int *p,i,j,max;
p = new int[len];
for(i = len-1; i >= 0;i--)
{
max = 0;
for(j = i+1;j < len;j++)
if(array[j] > array[i] && p[j] > max)max = p[j];
p[i] = max+1;
}
max = 0;
for(i = 0; i < len;i++)
if(p[i] > max) max = p[i];
delete[]p;
return max;
}
3 楼
iAkiak [专家分：8460] 发布于 2006-06-16 22:20:00
int maxclarray(int *array, int len)
{
int length[1000], i, j, max = 0;
for (i = 0; i < len; i++)
{
length[i] = 0;
for (j = i - 1; j >= 0; j--)
{
if (array[i] < array[j] && length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
if (length[i] > max)
max = length[i];
}
}
}
return max;
}
4 楼
sllone [专家分：150] 发布于 2006-06-16 22:28:00
int maxclarray(int *array,int len){
int *tmp=new int[len];
int s,max_s=1,k;
for(int i=len-1;i>=0;i--){
s=1;
for(int j=i+1;j<len;j++){
k=1;
if(array[i]<array[j]){
k+=tmp[j];
if(k>s)
s=k;
}
}
tmp[i]=s;
if(s>max_s)
max_s=s;
}
return max_s;
}
5 楼
fantasyzzz [专家分：0] 发布于 2006-06-16 23:15:00
int maxclarray(int *a,int len)
{
int max=1;
int temp=1;
for(int i=0;i<len-1;++i)
{
if(a[i+1]>a[i])
++temp;
else if(len-i<=temp)
break;
else if(temp>max)
{
max=temp;
temp=1;
}
}
if(temp>max)
max=temp;
return max;
}
6 楼
fantasyzzz [专家分：0] 发布于 2006-06-16 23:35:00
int maxclarray1(int *a,int len)
{
int max=0;
int start=0;
for(int i=0;i<len-1;++i)
{
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;
}
7 楼
pigeonoo [专家分：130] 发布于 2006-06-16 23:52:00
int maxclarray(int *array,int len)
{
int max=1,i=0,temp=1;
for (i=0;i<len-1;i++)
{
if(array[i]<array[i+1])
temp++;
else
temp=1;
if(temp>max)
max=temp;
}
return max;
}
8 楼
subchap [专家分：100] 发布于 2006-06-17 03:36:00
int maxclarray(int *array,int len)
{
int CurrentValue=array[len-1],CurrentPos=0,maxLen=0,CurrentLen=0;
while(CurrentPos<len)
{
if(CurrentValue<array[CurrentPos]||CurrentPos==0)
{
CurrentLen++;
}
else
{
if(CurrentLen>maxLen) maxLen=CurrentLen;
CurrentLen=1;
}
CurrentValue=array[CurrentPos];
CurrentPos++;
}
if(CurrentLen>maxLen) maxLen=CurrentLen;
return maxLen;
}
Dev-C++ 下编译通过
9 楼
darleter [专家分：0] 发布于 2006-06-17 10:23:00
/*一次走过全部数组，
但是数据之间的交换比较多，定义的变量也比较多。
希望能看到数据交换更少，使用变量更少得程序。
给出的程序的函数部分。
希望大家指正。
*/
int maxclarray(int *array,int len)
{
int i,length=1,head,end,count=0;
for(i=0;i<len-1;i++)
{
head=*(array+i);
end=*(array+i+1);
if(head < end)
{
length++;
}else
{
if(count < length)
count=length;
length=1;
}
}
return count;
}
10 楼
goal00001111 [专家分：4030] 发布于 2006-06-17 12:03:00
int maxclarray(int *array,int len)
{
int *t;//存储以a[i]为末元素的最长递增子序列长度
if (!(t = new int[len]))
{
cout << "fail!\n";
exit(1);
}
t[0]=1;//以a[0]为末元素的最长递增子序列长度为1；
for (int i=1; i<len; i++)//循环num-1次
{
t[i]=1;//t[i]的最小值为1；
if (array[i-1] < array[i])
t[i] = t[i-1]+1;//更新t[i]的值。
}
int max = 1;
for (int i=1; i<len; i++)
max = (max > t[i]) ? max : t[i];
delete []t;
return max;
}
我来回复
您所在位置：