Maximum subarray of bounded length
-
05-11-2019 - |
Pergunta
I'm giving an array $A[0..n-1]$ and an integer $w$. The goal is to find indices $i,j$ that maximize
$$\Phi(i,j) = A[i] + A[i+1] + \dots + A[j-1],$$
subject to the requirements that $0 \le i \le j \le n$ and $j \le i+w$. Or, in other words, I want to find the sequential window of width at most $w$ such that the sum of the numbers in the window is maximized.
Is there an $O(n)$ time algorithm for this task? Or, what is the most efficient algorithm for this task?
There is a trivial $O(nw)$ time algorithm, but I can't see how to do better than that. If $w=\infty$, Kadane's algorithm solves this in $O(n)$ time, but I can't see how to generalize it to my problem. So, can we do better than $O(nw)$ time?
I encountered this problem in the context of an image processing task I'm facing.
Nenhuma solução correta