# Maximal subarray problem with length constraint [duplicate]

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 |                           |
| 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$.

• This is a standard problem. What references have you checked? What have you tried and where did you get stuck? – Raphael Sep 8 '15 at 14:44
• @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. – Steve D Sep 8 '15 at 19:23
• @Raphael: If you have a reference that treats this case, I would be more than happy if you shared it with me. – Steve D Sep 8 '15 at 20:55