C++ 代码实现：查找最长可被7整除的区间

C++ 代码实现：查找最长可被7整除的区间

给定 n 个数，分别是 a[1], a[2], ..., a[n]。求一个最长的区间 [x, y]，使得区间中的数 (a[x], a[x+1], a[x+2], ..., a[y-1], a[y]) 的和能被 7 整除。输出区间长度。若没有符合要求的区间，输出 0。

输入描述

第一行一个整数 n (1 <= n <= 50000)，接下来是每一个整数

输出描述

一个最长的区间内容：[x, y] 的长度，使得区间中的数的和能被 7 整除。若没有符合要求的区间，输出 0。

样例输入

6
1
2
3
1
1
1

样例输出

3

提示

样例解释：区间 [2, 4] 中的数的和为 2 + 3 + 1 = 6，能被 7 整除，且长度为 3，是符合要求的最长区间。

代码实现

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[50001];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int sum = 0;
    int maxLen = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        for (int j = i; j <= n; j++) {
            sum += a[j];
            if (sum % 7 == 0) {
                maxLen = max(maxLen, j - i + 1);
            }
        }
        sum = 0;
    }

    cout << maxLen << endl;
    return 0;
}

代码解析

代码使用两个循环来枚举所有的区间。外层循环枚举区间的左端点，内层循环枚举区间的右端点。对于每个区间，计算区间内所有数的和，并判断该和是否能被 7 整除。如果能被 7 整除，则更新最大区间长度。最后输出最大区间长度。

时间复杂度

代码的时间复杂度为 O(n^2)，其中 n 为整数序列的长度。

空间复杂度

代码的空间复杂度为 O(n)，用于存储整数序列。