I tried to solve this problem but could not do it better than $O(n^2)$.
My Algorithm:
1. Calculate prefix sum
2. for i in 1..n:
for j in 1..i:
if presum[i] - presum[j-1] > k:
ans = max(ans, i - j)
Edit: I have found a solution which works in $O(n\log n)$. This solution does a binary search on the length of the subarray and chooses the maximum length of the subarray satisfying the property.
The code is as follows:
#include<stdio.h>
long long int a[1000005]={0},sum[1000005]={0},n,k;
long long int check(long long int len)
{
long long int i,c=0;
for(i=len;i<=n;i++)
{
if((sum[i]-sum[i-len])>=k)
c++;
}
return c;
}
int main()
{
long long int i;
scanf("%lld",&n);
scanf("%lld",&k);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum[i]=a[i]+sum[i-1];
}
long long int low=0,high=n,ans=0,count=0;
while(low<=high)
{
long long int mid=(low+high)/2;
long long int p=check(mid);
if(p>0)
{
ans=mid;
low=mid+1;
}
else
{
high=mid-1;
}
}
if(ans==0)
printf("-1\n");
else
printf("%lld\n",ans);
return 0;
}
My doubts: How does this algorithm discards the search space?
More specifically, what I want to know that suppose there does not exist any subarray of length $len$, then how can we show that there won't exist any subarray of length $>len$. The above code does the same way, whenever there does not exist any subarray of length $mid$ it removes the other half and continues to search for an answer in the lower half by decreasing the $high$ to $mid-1$.
1.
- without either 2., 0. or 1.1. that looks pointless.) How about accumulating postfix sums, too? $\endgroup$[100, 100, -100, -100, 100, 100]
Andk=50
, there exists a valid interval of length 3 and 5, but none with length 4. $\endgroup$