Maximum subarray problem with weights
Please check the following proof, and see the final remark with a link to code for an $O(n)$-time algorithm.
Theorem 1. There is an $O(n\log n)$-time algorithm for the problem.
Proof.
Fix an instance $(n, A, W)$ of the problem. Define index set $I = \{(i, j) : 1\le i\le j \le n\}$. The goal is to compute $\max_{(i,j)\in I} M_{ij}$, where
$$\textstyle M_{ij} = \Big(\sum_{h=i}^j A[h]\Big) - (j-i+1) W[j].$$
Observe that $M_{ij}$ has the (upper-triangular) inverse Monge property (see e.g. this survey on Monge matrices):
Lemma 1. For any $(i, j)$ and $(k, \ell)$ in $I$ such that $i&lt;k$ and $j &lt; \ell$, $$M_{i\ell} - M_{ij} \le M_{k\ell} - M_{kj}.$$
Proof of Lemma 1.  By calculation,
$$M_{i\ell} - M_{ij} = \Big(\sum_{h={j+1}}^\ell A[h]\Big) + (j-i+1) W[j] - (\ell-i+1) W[\ell],$$
while
$$M_{k\ell} - M_{kj} = \Big(\sum_{h={j+1}}^\ell A[h]\Big) + (j-k+1) W[j] - (\ell-k+1) W[\ell],$$
so
$$(M_{i\ell} - M_{ij}) - (M_{k\ell} - M_{kj}) =
(k-i) W[j] - (k - i) W[\ell] = (k-i)(W[j] - W[\ell]),$$
which is non-positive as $k &gt; i$, and $j&lt;\ell$ so $W[j] \le W[\ell]$.  This proves Lemma 1. $~~~\Box$
It is well-known (e.g. Section 3.7 of this survey) that the Monge property is sufficient to obtain a simple $O(n\log n)$-time algorithm, and it is easy to adapt that algorithm to the upper-triangular case.  For completeness I'll sketch the algorithm here.
Lemma 1 implies that $M$ is (upper-triangular) totally (inverse) monotone:
Corollary 1. For any $(i, j)$ and $(k, \ell)$ in $I$ such that $i&lt;k$ and $j &lt; \ell$, if $M_{ij} \le M_{i\ell}$ then $M_{kj} \le M_{kl}$.
For $1\le i \le n$, define $J(i) = \arg\max_{j} M_{ij}$ to be the column index of the maximum entry in row $i$.  Corollary 1 implies the following additional corollary:
Corollary 2. $J(1) \le J(2) \le \cdots \le J(n)$
The algorithm computes $J(i)$ for the middle row $i=\lfloor n/2 \rfloor$ in $O(n)$ time (having precomputed all partial sums of $A$ in $O(n)$ time, so that the value of any given $M_{ij}$ can be computed in constant time), then subdivides $M$ into four quadrants around the point $(i, J(i))$, recurses on the upper-left and lower-right quadrants, and takes either $(i, J(i))$ or one of the two points returned recursively, whatever is best.
(Note that the algorithm does not explicitly construct all of $M$.  In fact, it examines $O(n\log n)$ entries of $M$.)
By Corollary 2, the maximum cannot be in the upper-right or lower-left quadrant, so the algorithm is correct.
Letting $T(n, m)$ denote the worst-case runtime on an $n\times m$ index set, we have $$T(n, m) \le m + \max_{1\le j\le m} ~T(\lfloor n/2 \rfloor -1, j) + T(n - \lfloor n/2\rfloor, m-j+1)$$
and $T(1, m) \le m$.  For any execution of the algorithm, the recursion tree has $O(\log n)$ levels. Within a given level, letting $(n_j, m_j)$ denote the dimensions of the $j$th subproblem on that level, we have $\sum_j m_j = O(m)$, from which it follows that the total work for all subproblems on that level (outside of their recursive calls) is $O(m)$, so that $T(n, m) = O(m\log n)$. (This can also be easily verified by induction.) So the run-time of the top-level call is $T(n, n) = O(n\log n)$. $~~~\Box$
Remarks. The total monotonicity of $M$ (Corollary 1 above) probably also implies an $O(n)$-time algorithm via the SMAWK algorithm. (It would if $M$ was totally (inverse) monotone, instead of just &quot;upper-triangular&quot; totally inverse monotone.)  I don't know whether SMAWK applies in this case, but I'd guess so. EDIT: See comment below.
Note that the above proof requires neither the assumption $A[i] \ge W[i]$, nor the non-negativity of the $A[i]$'s and $W[i]$'s.
EDIT: It seems to me that we can extend $M$ to make it totally inverse Monge simply by taking $M_{ij}$ to be, say, $-n W[n]$, for $1\le j &lt; i \le n$.  Then we no longer require the &quot;upper triangular&quot; assumption: the property in Corollary 2 holds for all pairs $(i, j)$ and $(k, \ell)$ with $(1,1) \le (i, j) &lt; (k, \ell) \le (n, n)$.  That is, $M$ extended in this way is totally (inverse) monotone. So the SMAWK algorithm can be applied to this $M$ to solve the problem in $O(n)$ time.
A quick google search gives this Python implementation of the SMAWK algorithm by David Eppstein.  I adapted his code to solve your problem; here is my adaptation.