If you are not in the mood to go to the library right away, here is a simple description:
Subtract $\kappa$ from everything ($N$ operations).
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)!
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.
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.
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.
- Once you finish debugging the program and get some free time, follow Gerhard's advice :).