微软编程一小时--Longest Repeated Sequence

ゝ一世哀愁。 2022-08-26 12:14 141阅读 0赞

###  ###

### 题目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

样例输出

解析：该题的大致意思是找最长的连续数假如是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;
    }