c++ - log（n）時間で配列の任意の範囲の最大値を見つける方法は？

Question

例：配列：{1、5、2、3、2、10}

範囲：0-1回答：5範囲：2-4回答：3範囲：0-5回答：10など。

Answer 1

配列がソートされていない場合、要求していることを実行する方法はありません。

最大値を見つけるには、少なくとも範囲内のすべての要素を検査する必要があります。これにはO（n）が必要です。

データの何らかの前処理を許可すれば、それは簡単です。^{答えを使ってn2}ルックアップテーブルを作成することができます。次に、一定時間内の任意の範囲の最大値を見つけることができます。

Answer 2

不可能だよ。あなたはすべての要素を訪問しなければならないでしょう。

配列がアプリオリにソートされている場合、それはO（1）操作です。

Answer 3

こちらも参照してください: 数値の配列から最小値または最大値を取得する最良の方法は何ですか?

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

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