# UVA Problem: Subsequence(1121)

October 8, 2011

**Problem Explanation:**

This problem is very interesting. The main concern goes to develop a O(n) algorithm , else there is no way to avoid TLE.

I am explaning this problem with sample I/O. consider

10 15

5 1 3 5 10 7 4 9 2 8.

we need to sum up >=15 using fewest number of consecutive element.we need two iterator first and last.

s=15;

sum=0;

first=0;

last=0;

while(1)

{

while(sum<s)

{

add A[last] to sum and increament last;

}we get >=s using 5 element {5,1,3,5,10}.

Now,

while (sum>=s)

{

subtract A[first] to sum and increament first;

}diff=(last-1)- (first-1) + 1;

if(diff< minSeq)

{

minSeq=diff;

}

}

Advertisements

No comments yet