欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【TOJ 5065】最长连续子序列

程序员文章站 2022-07-02 11:46:38
Description 给定一系列非负整数,求最长的连续子序列,使其和是7的倍数。 Input 第一行为正整数N(1<=N<=50000),接下来有N行,每行有一个非负整数,所有整数不大于10^6。 Output 如果存在连续子序列,其和为7的倍数,则输出子序列长度,如果不存在则输出0。 Sampl ......

Description

给定一系列非负整数,求最长的连续子序列,使其和是7的倍数。

Input

第一行为正整数N(1<=N<=50000),接下来有N行,每行有一个非负整数,所有整数不大于10^6。

Output

如果存在连续子序列,其和为7的倍数,则输出子序列长度,如果不存在则输出0。

Sample input

7
3
5
1
6
2
14
10

Sample output

5

#include<iostream> 
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int n,i,j,a[50001],right[9],left[9],maxx=0,len;
    cin>>n;
    memset(right,-1,sizeof(right));
    memset(left,-1,sizeof(left));
    a[0]=0;
    left[0]=0;
    for(i=1;i<n;i++)
    {
        scanf("%d",&a[i]);
        a[i]=(a[i-1]+a[i])%7;
        if(left[a[i]]==-1)
        left[a[i]]=i;
    }
    for(i=n-1;i>=0;i--)
    {
        if(right[a[i]]==-1)
            right[a[i]]=i;
    }
    for(i=0;i<=8;i++)
    {
        for(j=0;j<=8;j++)
        {
            if(right[i]>=0&&left[j]>=0&&i==j)
            {
                len=right[i]-left[j];
                maxx=max(len,maxx);
            }
        }
    }
    cout<<maxx<<endl;
    return 0;
}