It makes me feel very old to say this, but what you are seeking is definitely an algorithm, not a formula. The bit that makes me feel very old is that I finished my computer science degree a quarter of a century ago. I can imagine Abe Simpson (Bart's Grandpa) saying this, but in my day, this is the sort of problem that we would have solved by writing an algorithm in Pascal using pencil and paper. Honestly, I can see the outline of the solution now. It involves 2 or 3 subroutines, and a bit of iteration in the main procedure -- most likely one for loop nested inside another, like:

for integer i = 1 to n
{
__for integer j = i to n
__{
__// This is where the main body of the logic would go.
__}
}

Yes, I know this is not Pascal. You can use any sensible notation to describe your algorithm. The leading underscores are simply because this discussion group software doesn't seem to like leading spaces or tabs.

I don't think there is any difficult performance analysis knowledge in this problem. Anybody bright enough to write the algorithm should be able to figure out that bit by themselves.

[Lapsing completely into Abe Simpson character...]
We used to solve a dozen problems like this in a one-hour tutorial. And we were grateful. :-)

__________________
Damien Laker is one of the world's leading authorities in performance analytics. For more information visit Moderators