The problem you are describing can be solved in $O(n)$.
Let's define the prefix sum as:
$$\text{psum}[i] = \sum_{0 \le j \le i} A[j]$$
Then your function can be expressed as:
$$\Phi(i, j) = \text{psum}[j-1] - \text{psum}[i-1]$$
Assuming we fix the right boundary $j-1$ (we want to find the window of size at most $w$ ending at $j-1$ with the maximal sum). It should be easy to see, that this window has the sum:
$$\text{psum}[j-1] - \min_{i \ge j - w}\left\{\text{psum}[i-1]\right\}$$
For the actuall implementation we use a data structure called Minimum Queue. It is a queue (FIFO) that does the normal push/pop operations in amortized constant time and it additionally supports extracting the minimum of its current stored elements in constant time.
With it we can find the maximal window in linear time:
best = 0
initialize min_queue
min_queue.push(psum[-1]) # psum[-1] can be defined as 0
for j = 1 to n:
if len(min_queue) > w:
min_queue.pop()
cur = psum[j-1] - min_queue.min()
best = max(best, cur)
min_queue.push(psum[j-1])
One way of implementing a Minimum Queue is to store the elements in a dequeue using value-index pairs. And you keep this queue in non-decreasing order, i.e. you only store the subset of pairs that are or can become the minimum at some point and ignore the remaining elements. This means whenever you push a new element, you remove all previous elements that are bigger from the back of the queue, since the currently added element will dominate them at all times. Therefore the minimum will always be the first element.
This approach, and also two (similar) alternatives are described on cp-algorithms.com.
