Java: finding index of maximum from slice of an array

I have a large array. I have some Java code for identifying indices for start and end points for a subset/slice of that large array. The only information items that I need to retrieve from the selected subsection of the array are the indices and values of the local maximum and minimum. What is the fastest (and least memory intensive) way that I can find a max and min within the specified range?

Here is a start of what I need in terms of code:

// Step One: declare new array and 开发者_Go百科populate it
pts = new double[5000];
for (int i = 0; i < 5000; i++){ pts[i] = (value assigned by extraneous process);}
// Step Two: slice out section between indices 3600 and 3750
    // what code do I write here?
// Step Three: find max value in the sliced section and return its index
    // what code to I write here?

---

Just iterate over the desired range and record maximum and minimum seen values:

double max = Double.NEGATIVE_INFINITY;
double min = Double.POSITIVE_INFINITY;
int minIndex = -1;
int maxIndex = -1;
for(int k = 3600; k < 3750; k++){
    if(max < pts[k]){
        max = pts[k];
        maxIndex = k;
    }else if(min > pts[k]){
        min = pts[k];
        minIndex = k;
    }
}

---

If it's not necessary to create a copy of the array for your slice, you can essentially do steps 2 and 3 in one fell swoop:

double max = pts[3600]; //the value of the first element in the slice
int maxIndex = 3600; //keep track of the index as you go. Assume at first
                     //that it is the first index of the slice
for(int i=3601; i<=3750; i++){
  if(pts[i] > max){  //you have encountered a larger element. Update the maxes
    max = pts[i];
    maxIndex = i;
  }
}
System.out.println("The max is " + max + " and occurred at index " + maxIndex);

(sorry for any syntax errors, I've been messing around with Scala and the grammar is a little different)

---

Have a loop that goes over the selected subsection once.

In the loop, adjust the values of four variables maxValue, maxIndex, minValue, minIndex as you find new maxima or minima.

After the loop, you will have the maximum and minimum and their positions.

No extra memory needed, linear performance (just one pass over the selected part of the array).

---

If you're going to do this a lot, you could increase performance by keeping track of the maxima / minima at different scales.

For instance if you keep a list for every 20 rows, and you want to check the range 55 - 184, you'd only need to check 5 values (55-59), then 6 values from 60-179, then 4 values from 180 - 184, so that's 15 checks rather than 130, a 20x speed increase.

Of course, you'd need to mark your buckets as changed when the array changes and periodically update them.