길이가 M이하인 Subarray들중 원소를 다 더한 값이 제일 큰것의 길이를 구해라.

A[i]=i에서 끝나는 subarray들중 원소를 다 더한 값이 제일 값이 큰 것이라고 하자.

그럼 문제에서 요구하는것은 max(A[0], …, a[n-1])이다.

각각의 a[i]는 max(max(-1,i-m)<=j<=i, prefixsum[i]-prefixsum[j]) 이고, prefixsum[i]를 밖으로 빼고 -안으로 집어넣으면 min으로 바껴서 prefixsum[i]-min(max(-1,i-m)<=j<=i, prefixsum[j])가 된다. Multiset이나 MonotonicQ같은 자료구조로 스위핑하면서 a[0]부터 a[n-1]까지 구할 수 있고 그러면 답 max(A[0], …, a[n-1])도 구할 수 있다.