2
$\begingroup$

I was recently faced with the following interview question:

Given an array A, and an integer k, find a contiguous subarray with a maximal sum, with the added constraint this subarray has length at most k.

So, if $A=[8, -1, -1, 4, -2, -3, 5, 6, -3]$ then we get the following answers for different values of $k$:

+---+------------------------------+
| k |           subarray           |
+---+------------------------------+
| 1 | [8]                          |
| 7 | [5,6]                        |
| 8 | [8, -1, -1, 4, -2, -3, 5, 6] |
+---+------------------------------+

If $n$ is the length of the array A, then using a modified priority queue, I was able to answer this question in time $O(n\lg k)$; is there a way to improve this to $O(n)$? Note that Kadane's algorithm runs in $O(n)$ time when $k=n$.

$\endgroup$
  • 1
    $\begingroup$ This is a standard problem. What references have you checked? What have you tried and where did you get stuck? $\endgroup$ – Raphael Sep 8 '15 at 14:44
  • $\begingroup$ @raphael: I checked in Cormen's book, which treated the usual case; this was true of everything I could find online as well. I didn't really "get stuck", just curious if there is a more efficient solution. $\endgroup$ – Steve D Sep 8 '15 at 19:23
  • $\begingroup$ @Raphael: If you have a reference that treats this case, I would be more than happy if you shared it with me. $\endgroup$ – Steve D Sep 8 '15 at 20:55