2
$\begingroup$

This question already has an answer here:

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$

marked as duplicate by D.W. algorithms Mar 19 at 5:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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