USACO 2016 January Contest, Silver Problem 2. Subsequences Summing to Sevens

http://www.usaco.org/index.php?page=viewproblem2&cpid=595#

題目大意：求出一個最長的序列，其中這個序列的和 mod 7 == 0。

把前綴和%7儲存起來，然後稍微比對，如果某兩個前綴和%7一樣，那這中間的數字和也一定%7 == 0！

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 50010;
int pre[MAX_N];

const int INF = 32653475;

int main () {
    freopen("div7.in","r",stdin);
    freopen("div7.out","w",stdout);
    int n;
    while (scanf("%d",&n) != EOF) {
        memset(pre,0,sizeof(pre));
        int g;
        int prepos[7],sufpos[7];
        for (int x=0;7>x;x++) prepos[x]=sufpos[x]=INF;
        prepos[0]=0;
        sufpos[0]=0;
        for (int x=1;n>=x;x++) {
            scanf("%d",&g);
            g%=7;
            pre[x]=pre[x-1] + (g%7);
            pre[x]%=7;
            if (prepos[pre[x]]==INF) {
                prepos[pre[x]]=x;
            }
            sufpos[pre[x]] = x;
        }
        int ans=-1;
        for (int x=0;7>x;x++) {
            if (sufpos[g]==INF || prepos[g]==INF) continue;
            if (sufpos[g]==0) continue;
            ans=max(ans,sufpos[x]-prepos[x]);
        }
        printf("%d\n",ans);
    }
}