この問題は尺取法により解くことができます。

尺取法

区間に対する条件 \(f\) が以下をともに満たすとする。

• \(r\) に関する単調性：任意の \(l\) に対してある \(r\) が存在して、\(r'\leq r\) ならば \(f([l,r'])\) は真であり、\(r' > r\) ならば \(f([l,r'])\) は偽である
• \(l\) に関する単調性：任意の \(r\) に対してある \(l\) が存在して、\(l \leq l'\) ならば \(f([l',r])\) は真であり、\(l'<l\) ならば \(f([l',r])\) は偽である
• 差分計算：\([l,r]\) に関する情報であって、以下の3つを満たすものが存在する
  • \(f([l,r])\) を高速に求められる
  • \([l+1,r]\) に関する情報を高速に求められる
  • \([l,r+1]\) に関する情報を高速に求められる

このとき、\(f([l,r])\) が真となる極大な区間 \([l,r]\) を以下の方法で列挙することができる。

// 閉区間 [left, right] を管理
while right < N:
  rightを追加する
  while f([left,right])が偽:
    leftを縮める
    left+=1
  /*区間 [left, rihgt] に対するなんらかの処理*/
  right+=1

解法

現時点の区間和を持ちながら尺取法を行えばよいです。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  long long k;
  cin >> n >> k;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  int ans = 0;
  long long crr = 0;
  int l = 0;
  for(int r=0; r<n; r++){
    crr += a[r];
    while(crr > k){
      crr -= a[l];
      l++;
    }
    ans = max(ans, r - l + 1);
  }
  cout << ans << endl;
}

実装例 (Python)

N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
crr = 0
l = 0
for r in range(N):
  crr += A[r]
  while crr > K:
    crr -= A[l]
    l += 1
  ans = max(ans, r - l + 1)

print(ans)