微软编程一小时--Longest Repeated Sequence-蒲公英云

微软编程一小时--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;
}