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

ゝ一世哀愁。 2022-08-26 12:14 206阅读 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.

样例输入

  1. 5
  2. 2 3 2 3 2

样例输出

  1. 2
  2. 解析:该题的大致意思是找最长的连续数假如是ai, ai+1 ... aj,这些数满足这样的条件: ai+k = ai, ai+k+1 = ai+1, ... aj+k = aj,也就是每个
  3. 数隔k个数就相同,但是还有一个条件i+k>j,这个也应该考虑到,综上我就直接模拟了一下,因为时间过了无法提交,如果有错请大家纠正哈!
  4. #include <iostream>
  5. using std::endl;
  6. using std::cin;
  7. using std::cout;
  8. int main(void)
  9. {
  10. int N;
  11. int data[300];
  12. while(cin >> N)
  13. {
  14. int maxLength=0;
  15. //输入数据
  16. for(int i=0; i<N; ++i)
  17. {
  18. cin >> data[i];
  19. }
  20. for(int i=0; i<N; ++i)
  21. {
  22. //如果没有与当前相等data[i],则k为初值
  23. int k = 0;
  24. //每一次循环计算length都应该重置
  25. int length = 0;
  26. //计算k
  27. for(int j=i+1; j<N; ++j)
  28. {
  29. if(data[j] == data[i])
  30. {
  31. length++;
  32. k = j-i;
  33. break;
  34. }
  35. }
  36. //开始计算长度
  37. for(int j=i+1; j+k<N;++j)
  38. {//这里还必须控制一个条件i + k > j
  39. if((data[j] == data[j+k]) && (i +k >j))
  40. {
  41. length++;
  42. }else{
  43. //如果不满足上述任何一个条件,终止循环
  44. break;
  45. }
  46. }
  47. //判断当前的计算的length与maxLength相比较
  48. if(length > maxLength)
  49. {
  50. maxLength = length;
  51. }
  52. }
  53. cout << maxLength << endl;
  54. }
  55. return 0;
  56. }

发表评论

表情:
评论列表 (有 0 条评论,206人围观)

还没有评论,来说两句吧...

相关阅读