前缀和 + 二分

1.先得到前缀和
2.使用"二分"得到每段"子连续区间"里的最大连续数，并记录
    注意二分条件的确定: 因为是要找到最大区间，所以条件为s[mid] - s[i - 1] <= t
    反过来写的话s[mid] - s[i - 1] >= t 则找到的是第一个大于等于t的连续区间，这个区间并非最大区间
写法1:
    for (int i = 1; i <= n; i++)
    {
        int l = i - 1, r = n + 1;
        while (l + 1 != r)
        {
            int mid = l + r >> 1;
            if (s[mid] - s[i - 1] <= t) l = mid;
            else r = mid;
        }
        res = max(res, l - i + 1);
    }
写法2(下文示例代码的写法):
    for (int i = 1; i <= n; i++)
    {
        int l = i - 1, r = n + 1;
        while (l + 1 != r)
        {
            int mid = l + r >> 1;
            if (s[mid] - s[i - 1] > t) r = mid;
            else l = mid;
        }
        res = max(res, l - i + 1);
    }

3.时间复杂度(n * logn)

#include <iostream>

using namespace std;

const int N = 1E6 + 10;

int a[N], s[N];

int main()
{
    int n, t;
    cin >> n >> t;

    // 前缀和
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int l = i - 1, r = n + 1;
        while (l + 1 != r)
        {
            int mid = l + r >> 1;
            if (s[mid] - s[i - 1] <= t) l = mid;
            else r = mid;
        }
        res = max(res, l - i + 1);
    }

    cout << res << endl;

    return 0;
}

尺取法(双指针)

维护两个指针i, j使得两个指针的区间总和 < t

#include <iostream>

using namespace std;

const int N = 1E6+10;

int w[N];

int main()
{
    int n, t;
    cin >> n >> t;

    for(int i = 0; i < n; i ++) cin >> w[i];

    int res = 0, sum = 0;
    for(int i = 0, j = 0; j < n; j ++)
    {
        sum += w[j];
        if(sum > t) 
        {
            sum -= w[i];
            i ++;
        }
        res = max(res, j - i + 1);
    }

    cout << res << endl;

    return 0;
}