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

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top