2019.7.24

Arkady invited Anna for a dinner to a sushi restaurant. The restaurant is a bit unusual: it offers n pieces of sushi aligned in a row, and a customer has to choose a continuous subsegment of these sushi to buy.

The pieces of sushi are of two types: either with tuna or with eel. Let's denote the type of the i-th from the left sushi as ti, where ti=1 means it is with tuna, and ti=2 means it is with eel.

Arkady does not like tuna, Anna does not like eel. Arkady wants to choose such a continuous subsegment of sushi that it has equal number of sushi of each type and each half of the subsegment has only sushi of one type. For example, subsegment [2,2,2,1,1,1] is valid, but subsegment [1,2,1,2,1,2] is not, because both halves contain both types of sushi.

Find the length of the longest continuous subsegment of sushi Arkady can buy.

Input
The first line contains a single integer n (2≤n≤100000) — the number of pieces of sushi.

The second line contains n integers t1, t2, ..., tn (ti=1, denoting a sushi with tuna or ti=2, denoting a sushi with eel), representing the types of sushi from left to right.

It is guaranteed that there is at least one piece of sushi of each type. Note that it means that there is at least one valid continuous segment.

Output
Print a single integer — the maximum length of a valid continuous segment.

Examples
Input
7
2 2 2 1 1 2 2
Output
4
Input
6
1 2 1 2 1 2
Output
2
Input
9
2 2 1 1 1 2 2 2 2
Output
6

我的思路：

用一個(gè)一維數(shù)組a存儲(chǔ)壽司的種類，再另開一個(gè)f數(shù)組,用一個(gè)for循環(huán)把a(bǔ)數(shù)組遍歷一遍礼预，如果第i個(gè)和第i+1個(gè)數(shù)不同步藕，就把a(bǔ)數(shù)組該元素的下標(biāo)加一標(biāo)記進(jìn)f數(shù)組里；再用一個(gè)for循環(huán)計(jì)算f數(shù)組里相鄰兩項(xiàng)元素的差值，將最大的差值存入一個(gè)變量max里面，最后輸出兩倍max即為所求。

#include <iostream>
using namespace std;
int main()
{
    int i,n,l1,l2;
    int a[100005]={0};
    int f[100005]; 
    f[0]=0;  //用來計(jì)算第一個(gè)輸入的壽司種類的個(gè)數(shù)
    cin >> n;
    int max=-1, j=1;
    int m;
    for(i=0; i<n; i++)
    {
        cin >> a[i];
    }
    
    for(i=0; i<n-1; i++)
    {
        if(a[i] != a[i+1])
        {
            f[j]=i+1;
            j++;
        }
        f[j]=n;
    }
    
    if(j>1)
    {
        for(int i=1; i<j; i++)
        {
            l1=f[i]-f[i-1];
            l2=f[i+1]-f[i];
            m = (l1>=l2)?l2:l1;
            if(m>max)
                max=m;
        }
        cout << max*2;
    }
    else
        cout << "0";
    return 0;
}