2
$\begingroup$

Given a sequence of integers ( +ve and/or -ve) $A_1, A_2, \ldots, A_n$, I need to find the smallest subsequence $A_i,\ldots, A_j$ whose sum is at least M.

How would the algorithm for the same go if I need a complexity of $O(n\log n)$ or at-most $O(n)$?

  • 1
    How do you define subsequence? Is it $A_{i},A_{i+1}, A_{i+2}, \dots, A_j$ or is it $A_{i_1}, A_{i_2}, ..., A_{i_n}$? I am guessing the former.2011-07-14

1 Answers 1

3

Consecutive case

Hint for $O(n\log n)$: calculate partial sums and use binary search.

Hint for $O(n)$: keep two pointers into the list and advance them alternately.

Non-consecutive case

Hint for $O(n\log n)$: sort the numbers and use binary search.

Hint for $O(n)$: find the median, calculate the sum of the upper half, and recurse on the appropriate half.

  • 0
    @Yuval, nice. :)2011-07-18