log（n）時間内にアレイのどの範囲で最大値を見つけるか？

Question

など。配列：{1,5、2、3、2、10}

範囲：0-1答え：5 範囲：2-4回答：3 範囲：0-5回答：10 等

Answer 1

配列がソートされていない場合は、あなたが求めていることをする方法がありません。 にあなたは少なくとも必要最大値を見つけるには

はO（nはを）取る範囲ですべての要素を点検します。

データの前処理を許可すると簡単です。あなたは答えを使ってn ルックアップテーブルを構築することができます。次に、一定の時間内に任意の範囲の最大値を見つけることができます。

Answer 2

これは不可能です。すべての要素を訪問する必要があります。

あなたの配列が先験的にソートされている場合は、O（1）操作です。

Answer 3

もここを参照してください： What is the best way to get the minimum or maximum value from an Array of numbers?

他の人が指摘したように、それは不可能だ

Answer 4

@Daniel Talamas私が正しくあなたを理解している場合、あなたはこの欲しかっ：あなたがすることはできません

#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; 
}