문제

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.

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top