Editing with response to comments:

I'm not sure what you guys are doing that it doesn't work for you, but here how it runs on

2 2 -1000 -1000 2 2 -2 2 2 2 2 -2 -2 2 2 -1000 -1000 2 2 2

with average 2:

Step 1: remove 2:

0,0,-1002,-1002,0,0,-4,0,0,0,0,-4,-4,0,0,-1002,-1002,0,0,0

Step 1: partial summation left to right:

0,0,0,-1002,-2004,-2004,-2004,-2008,-2008,-2008,-2008,-2008,-2012,-2016,-3018,-4020,-4020,-4020,-4020.

Step 3:

Min positions (strict!) counting from the left:

0: 0, 3: -1002, 4: -2004, 7: -2008, 12: -2012, 13: -2016, 14: -3018, 15: -4020,

Max positions (strict) counting from the right:

2: 0, 3: -2002, 6: -2004, 11: -2008, 12: -2012, 13: -2016, 14: -3018, 18: -4020,

Steps 4,5. Put the marker B (beginning-1) and E (end) at the leftmost possible positions: B=0,E=2. Record the length 2 and the interval [1,2]

Try moving E to the right with this B. Impossible.

Change B to 3 (value -1002). Try to move E to the right. Impossible

B=4 (-2004) Now E can go to te right to 6 (-2004). Same length. No record.

B=7 (-2008) E goes (from the previous position, not from the beginning!) to 11 (-2008) Length 4>2, interval [8,11]. Record.

B=12 (-2012) E goes to 12. Length 0, no record.

B=13 (-2016), E goes to 13. Length 0, no record.

B=14 (-3018), E goes to 14. Length 0, no record.

B=15 (-4020), E goes to 18. Length 3<4, no record, reached the end, terminate, output [8,11].

If you are not in the mood to go to the library right away, here is a simple description:

1. Subtract $\kappa$ from everything ($N$ operations).

2. Replace $a_k$ by the partial sums $S_k=\sum_{j=1}^k a_j$ ($N$ operations).

Now you are looking for the pair $0\le k<m\le N$ such that $S_k\le S_m$ with the largest difference $m-k$. Note that $S_k$ is necessarily the minimum of $S_1,\dots,S_k$ and $S_m$ is necessarily the maximum of $S_m,S_{m+1},\dots,S_{N-1}$. Don't forget $S_0$ (the empty sum)!

3. Mark all such minima going from the left and all such maxima going from the right ($5N$ operations or so). You will have a decreasing sequence of positive starting positions and a decreasing sequence of positive ending positions.

4. Start with the leftmost starting position and go along the possible ending positions from the left to the right until you get the rightmost that still works. Record the difference. Go to the next starting position and see how far you can move the ending position to fit now. Compare the difference with the previous one and record it if it is larger.

5. Repeat until you reach the end.

Note that you go left to right all the time never coming back, so these steps are linear as well. Probably, you can optimize a bit but I'm too lazy to think of how.

6. Once you finish debugging the program and get some free time, follow Gerhard's advice :).

If you are not in the mood to go to the library right away, here is a simple description:

1. Subtract $\kappa$ from everything ($N$ operations).

2. Replace $a_k$ by the partial sums $S_k=\sum_{j=1}^k a_j$ ($N$ operations).

Now you are looking for the pair $0\le k\le m\le N$ such that $S_k\le S_m$ with the largest difference $m-k$. Note that $S_k$ is necessarily the minimum of $S_1,\dots,S_k$ and $S_m$ is necessarily the maximum of $S_m,S_{m+1},\dots,S_{N-1}$. Don't forget $S_0$ (the empty sum)!

3. Mark all such minima going from the left and all such maxima going from the right ($5N$ operations or so). You will have a decreasing sequence of positive starting positions and a decreasing sequence of positive ending positions.

4. Start with the leftmost starting position and go along the possible ending positions from the left to the right until you get the rightmost that still works. Record the difference. Go to the next starting position and see how far you can move the ending position to fit now. Compare the difference with the previous one and record it if it is larger.

5. Repeat until you reach the end.

Note that you go left to right all the time never coming back, so these steps are linear as well. Probably, you can optimize a bit but I'm too lazy to think of how.

6. Once you finish debugging the program and get some free time, follow Gerhard's advice :).