<p>This is a good application of a <strong>min-queue</strong> - a queue (First-In, First-Out = FIFO) which can simultaneously keep track of the minimum element it contains, with amortized constant-time updates.  Of course, a max-queue is basically the same thing.</p>

<p>Once you have this data structure in place, you can consider CurrentMax (of the past 1000 elements) minus CurrentMin, store that as the BestSoFar, and then push a new value and pop the old value, and check again.  In this way, keep updating BestSoFar until the final value is the solution to your question.  Each single step takes amortized constant time, so the whole thing is linear, and the implementation I know of has a good scalar constant (it's fast).</p>

<p>I don't know of any documentation on min-queue's - this is a data structure I came up with in collaboration with a coworker.  You can implement it by internally tracking a binary tree of the least elements within each contiguous sub-sequence of your data.  It simplifies the problem that you'll only pop data from one end of the structure.</p>

<p>If you're interested in more details, I can try to provide them.  I was thinking of writing this data structure up as a paper for arxiv.  Also note that Tarjan and others previously arrived at a more powerful min-deque structure that would work here, but the implementation is much more complex.  You can <a href="http://www.google.com/search?q=mindeque" rel="noreferrer">google for "mindeque"</a> to read about Tarjan et al.'s work.</p>
Algorithm for finding the maximum difference in an array of numbers
<p>I have an array of a few million numbers.</p>

<pre><code>double* const data = new double (3600000);
</code></pre>

<p>I need to iterate through the array and find the range (the largest value in the array minus the smallest value). However, there is a catch. I only want to find the range where the smallest and largest values are within 1,000 samples of each other.</p>

<p>So I need to find the maximum of: range(data + 0, data + 1000), range(data + 1, data + 1001), range(data + 2, data + 1002), ...., range(data + 3599000, data + 3600000).</p>

<p>I hope that makes sense. Basically I could do it like above, but I'm looking for a more efficient algorithm if one exists. I think the above algorithm is O(n), but I feel that it's possible to optimize. An idea I'm playing with is to keep track of the most recent maximum and minimum and how far back they are, then only backtrack when necessary.</p>

<p>I'll be coding this in C++, but a nice algorithm in pseudo code would be just fine. Also, if this number I'm trying to find has a name, I'd love to know what it is.</p>

<p>Thanks.</p>