Monday, June 16, 2014

Smallest subarray with sum greater than a given value



static int findSmallestSubArrayLen(int[] arr, int x){

int len = arr.length;

int sum = 0, min = len, r = 0,rear = 0,front = 0;

for(int i = 0; i<len; i++)
{
sum += arr[i];
if(sum > x)
{
for(; r <= i; )
{
if(sum > x)
{
if(min > i-r+1){
min = i-r+1;
rear = r;
front = i;
}
sum -= arr[r++];
}else break;
}
}
}
if(min != len){
while(rear<=front){
System.out.print(arr[rear++]+",");
}
return min;
}

else return -1;
}

Reference:

http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

No comments:

Post a Comment