假設我得到以下陣列
a = [4 5 2 1 3 4]
我想找到兩個元素（最大和最小）之間的差異，但不包括一些連續的元素。
例如，排除了第2個和第3個，所以我需要找到以下的最大/最小之差：
a = [4 1 3 4 ]
在這種情況下，它是
diff = 41
現在，我正在尋找一種有效的演算法，可以反復地做這個。 我正在考慮有一個前綴和后綴，但不知道如何推進
uj5u.com熱心網友回復：
只是掃描陣列。存盤最小和最大值，同時忽略那些被排除在外的值。
uj5u.com熱心網友回復：
所以我們有一個陣列。
所以我們有一個大小為N的陣列a和M這種形式的查詢。"除去區間[L, R]，a中的最大和最小元素之間有什么區別？"。考慮到我們有一個有效的方法來查詢任意區間[X, Y]上的最小和最大值，那么我們可以使用下面的演算法：
- 在區間
[0, L)上查詢最小/最大。
- 在區間
(R, N)上查詢最小/最大。
- 將兩個區間的最小和最大值合并 。
- 減去這兩個 。
后期編輯：我最初提出的解決方案要比必要的復雜得多。如果你對其他方法感到好奇，我就不說了，但這里有一個更簡單的方法。
由于我們知道我們將始終只查詢[0, something)和(something, N)形式的區間，我們可以在線性時間內預先計算出最小/最大值。考慮像這樣存盤它們：
min_from_left[i] = 最小專案，只考慮專案0..i
min_from_right[i] = 只考慮i...N項的最小專案
相同的for max
現在，排除區間[L, R]的最小值是min(min_from_left[L-1], min_from_right[R 1])（我省略了邊界檢查）。因此，你可以實作O(N)的預計算和O(1)的每次查詢。
通用（但不必要的方法）
為了找到給定區間內的最小/最大值，你有很多選擇，這只取決于你的時間和記憶體限制是什么，以及你是否需要更新：
為了找到給定區間內的最小/最大值，你有很多選擇。
一般來說，如果你需要更新，你可以獲得O(N M * log N)時間復雜性，如果你不需要更新，則可以獲得O(N log N M)。
在這里看到更多的選擇https://cp-algorithms.com/sequences/rmq.html
uj5u.com熱心網友回復：
這有用嗎？
這有用嗎？
#include <iostream>
使用 命名空間 std.com.cn>。
int main()
{
int arr[6] = { 4, 5, 2, 1, 3, 4 };
int max = arr[0], min = arr[0] 。
int first, second;
cout << "輸入范圍（第一個值）。"。
cingt;> first; //在你的例子中，first = 1 。
cout << "輸入范圍（最后值）。"。
cingt;> second; //第二=2，在你的例子中。
for (int i = 0; i < 6; i )
{
if (i >= first & & i <= second)
繼續。
if (arr[i] < min)
min = arr[i];
if (arr[i] > max)
max = arr[i];
}
cout << "max和min之間的差異是" << max - min << endl。
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/325801.html
標籤：
上一篇：演算法的分析和時間方程的建立？