微软编程一小时--Longest Repeated Sequence
#
题目2 : Longest Repeated Sequence
时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB
描述
You are given a sequence of integers, A = a1, a2, … an. A consecutive subsequence of A (say ai, ai+1 … aj) is called a “repeated sequence” if it appears more than once in A (there exists some positive k that ai+k = ai, ai+k+1 = ai+1, … aj+k = aj) and its appearances are not intersected (i + k > j).
Can you find the longest repeated sequence in A?
输入
Line 1: n (1 <= n <= 300), the length of A.
Line 2: the sequence, a1 a2 … an (0 <= ai <= 100).
输出
The length of the longest repeated sequence.
样例输入
5
2 3 2 3 2
样例输出
2
解析:该题的大致意思是找最长的连续数假如是ai, ai+1 ... aj,这些数满足这样的条件: ai+k = ai, ai+k+1 = ai+1, ... aj+k = aj,也就是每个
数隔k个数就相同,但是还有一个条件i+k>j,这个也应该考虑到,综上我就直接模拟了一下,因为时间过了无法提交,如果有错请大家纠正哈!
#include <iostream>
using std::endl;
using std::cin;
using std::cout;
int main(void)
{
int N;
int data[300];
while(cin >> N)
{
int maxLength=0;
//输入数据
for(int i=0; i<N; ++i)
{
cin >> data[i];
}
for(int i=0; i<N; ++i)
{
//如果没有与当前相等data[i],则k为初值
int k = 0;
//每一次循环计算length都应该重置
int length = 0;
//计算k
for(int j=i+1; j<N; ++j)
{
if(data[j] == data[i])
{
length++;
k = j-i;
break;
}
}
//开始计算长度
for(int j=i+1; j+k<N;++j)
{//这里还必须控制一个条件i + k > j
if((data[j] == data[j+k]) && (i +k >j))
{
length++;
}else{
//如果不满足上述任何一个条件,终止循环
break;
}
}
//判断当前的计算的length与maxLength相比较
if(length > maxLength)
{
maxLength = length;
}
}
cout << maxLength << endl;
}
return 0;
}
还没有评论,来说两句吧...