-1

E.g. Array: {1, 5, 2, 3, 2, 10}

Range: 0-1 Answer: 5 Range: 2-4 Answer: 3 Range: 0-5 Answer: 10 etc.

thesquaregroot
  • 1,414
  • 1
  • 21
  • 35
Daniel Talamas
  • 81
  • 1
  • 5
  • 4
    You can't. In order to find the maximum in an unsorted sequence, you will have to look at each value at least once. That makes the algorithm O(n). – sbi Feb 27 '12 at 15:08
  • @sbi: Unless you preprocess the array and build a search tree/table/whatever to give the maximum of any subrange more quickly than searching the subrange. Presumably, that's what the question is asking about, although it's a bit terse. – Mike Seymour Feb 27 '12 at 15:11
  • 1
    @Mike: While that is true, I wouldn't call such a beast an "unsorted sequence". I did leave this loophole intentionally, you know? `:)` – sbi Feb 27 '12 at 15:14
  • 1
    have you considered building a quantum computer to do that? – PlasmaHH Feb 27 '12 at 15:23
  • you can take a look at my comment. – ddacot Feb 27 '12 at 15:34
  • http://wcipeg.com/wiki/Range_minimum_query gives several algorithms. The optimal is linear preprocessing time plus constant query time. – misterbee Jan 19 '14 at 20:34

4 Answers4

11

If the array is not sorted, then there is no way to do what you're asking for.

To find the maximum you at least need to inspect all elements in the range, which takes O(n).

If you allow some form of preprocessing of the data, it's easy. You could just build an n2 lookup table with the answers. Then you could find the maximum for any range in constant time.

aioobe
  • 413,195
  • 112
  • 811
  • 826
4

This is impossible. You'd have to visit every element.

If your array is sorted a-priori, then it's O(1) operation.

GregC
  • 7,737
  • 2
  • 53
  • 67
1

See also here: What is the best way to get the minimum or maximum value from an Array of numbers?

As the others pointed out it's impossible

Community
  • 1
  • 1
Azrael3000
  • 1,847
  • 12
  • 23
0

@Daniel Talamas if i understood you correctly, you wanted this : 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int maxlement(int range1,int range2) {
std::vector<int> v{ 1, 5, 2, 3, 2, 10 };
std::vector<int>::iterator result;

result = std::max_element(v.begin()+range1, v.begin()+range2+1);
int dist = std::distance(v.begin(), result);
return v[dist];

}
int main() {
int range1,range2;
cout<<"From ";
cin>>range1;
cout<<"To ";
cin>>range2;
cout<<"Max Element Is "<<maxlement(range1,range2);
return 0;
}
ddacot
  • 1,212
  • 3
  • 14
  • 40