Sous-réseau maximum de longueur limitée

Question

Je donne un tableau $ A [0..n-1] $ Et un entier $ w $. Le but est de trouver des indices $ i, j $ qui maximisent

$$ phi (i, j) = a [i] + a [i + 1] + Dots + a [j-1], $$

sous réserve des exigences qui $ 0 le i le j le n $ et $ j le i + w $. Ou, en d'autres termes, je veux trouver la fenêtre séquentielle de largeur au plus $ w $ de telle sorte que la somme des nombres dans la fenêtre soit maximisée.

Y'a-t-il un $ O (n) $ Algorithme de temps pour cette tâche? Ou, quel est l'algorithme le plus efficace pour cette tâche?

Il y a un trivial $ O (nw) $ Algorithme de temps, mais je ne vois pas comment faire mieux que ça. Si $ w = infty $, L'algorithme de Kadane résout ceci $ O (n) $ Le temps, mais je ne vois pas comment le généraliser à mon problème. Alors, pouvons-nous faire mieux que $ O (nw) $ temps?

J'ai rencontré ce problème dans le contexte d'une tâche de traitement d'image auxquelles je suis confronté.