首页 > 试题广场 >

(两元序列)试求一个整数序列中,最长的仅包含两个不同整数的连

[填空题]
(两元序列)试求一个整数序列中,最长的仅包含两个不同整数的连续子序列。如有多个子序列并列最长,输出任意一个即可。例如,序列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中,有两段满足条件的最长子序列,长度均为 7,分别用下划线和上划线标出。

#include <stdio.h>
int main( ) {
    const int SIZE = 100;
    int n, i, j, a[SIZE], cur1, cur2, count1, count2,
            ans_length, ans_start, ans_end;
    //cur1, cur2分别表示当前子序列中的两个不同整数
    //count1, count2分别表示 cur1, cur2在当前子序列中出现的次数
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    i = 1;
    j = 1;
    //i, j分别表示当前子序列的首尾,并保证其中至多有两个不同整数
    while ((j <= n) && (a[j] == a[i]))
        j++;
    cur1 = a[i];
    cur2 = a[j];
    count1 = 1; //(3 分)
    count2 = 1;
    ans_length = j - i + 1;
    while (j < n) {
        j++;
        if (a[j] == cur1)
            count1++;
        else if (a[j] == cur2)
            count2++;
        else {
            if (a[j - 1] == 2) { //(3 分)
                while (count2 > 0) {
                    if (a[i] == cur1)
                        count1--;
                    else
                        count2--;
                    i++;
                }
                cur2 = a[j];
                count2 = 1;
            } else {
                while (count1 > 0) {
                    if (a[i] == cur1)
                        3; //(2 分)
                    else
                        4; //(2 分)
                    i++;
                }
                5; //(3 分)
                count1 = 1;
            }
        }
        if (ans_length < j - i + 1) {
            ans_length = j - i + 1;
            ans_start = i;
            ans_end = j;
        }
    }
    for (i = ans_start; i <= ans_end; i++)
        printf("%d ", a[i]);
    return 0;
} 

这道题你会答吗?花几分钟告诉大家答案吧!