題目：給出一個數組A，找出一對 (i, j)使得A[i] <= A[j] (i <= j)並且j-i最大 ，若有多個這樣的位置對，返回i最小的那一對。
最直接的想法就是對於每一個 i 從數組最尾端開始向前找到第一個大於等於 A[i] 的位置 j ，時間復雜度O(n^2)。
[cpp] pair<int, int> find(const vector<int> &A)
{
int n = A.size();
if(n == 0)
throw new invalid_argument("Array's size can't be 0!");
int target_i = 0, target_j = 0;
int max_len = 0;
for(int i = 0; i < n; ++i)
{
int j;
for(j = n-1; j >= i; --j)
if(A[j] >= A[i])
break;
if(j-i+1 > max_len)
{
target_i = i;
target_j = j;
max_len = j-i+1;
}
}
return make_pair<int, int>(target_i, target_j);
}
pair<int, int> find(const vector<int> &A)
{
int n = A.size();
if(n == 0)
throw new invalid_argument("Array's size can't be 0!");
int target_i = 0, target_j = 0;
int max_len = 0;
for(int i = 0; i < n; ++i)
{
int j;
for(j = n-1; j >= i; --j)
if(A[j] >= A[i])
break;
if(j-i+1 > max_len)
{
target_i = i;
target_j = j;
max_len = j-i+1;
}
}
return make_pair<int, int>(target_i, target_j);
}
我們對上述算法稍作優化。當i=0時，我們假設找到的大於A[i]的最右位置是j0，那麼對於i=1時，我們根本就不需要考慮小於j0的位置，因為它們的區間長度都小於j0+1，不可能成為最優解。
[cpp] pair<int, int> find(const vector<int> &A)
{
int n = A.size();
if(n == 0)
throw new invalid_argument("Array's size can't be 0!");
int target_i = 0, target_j = 0;
int max_len = 0;
for(int i = 0; i < n; ++i)
{
int j;
for(j = n-1; j > target_j; --j) // 此處只需檢查到target_j
if(A[j] >= A[i])
break;
if(j-i+1 > max_len)
{
target_i = i;
target_j = j;
max_len = j-i+1;
}
}
return make_pair<int, int>(target_i, target_j);
}
pair<int, int> find(const vector<int> &A)
{
int n = A.size();
if(n == 0)
throw new invalid_argument("Array's size can't be 0!");
int target_i = 0, target_j = 0;
int max_len = 0;
for(int i = 0; i < n; ++i)
{
int j;
for(j = n-1; j > target_j; --j) // 此處只需檢查到target_j
if(A[j] >= A[i])
break;
if(j-i+1 > max_len)
{
target_i = i;
target_j = j;
max_len = j-i+1;
}
}
return make_pair<int, int>(target_i, target_j);
}
但時間復雜度仍然是O(n^2)的。我們可以繼續接著上面的思路優化。其實對於位置 i 求最後一個大於等於它的位置，不需要每次都從數組尾部向前找，我們可以通過改進這個地方將時間復雜度變為O(n)。
過程是這樣的，對於 i ，我們先找到 i 及其右端的最大元素的位置 j ，檢查是否比當前記錄的最優解更優，更新。然後考慮 j+1及其右端的最大元素位置是否大於等於A[i]，若是，令 j 等於該位置，重復如上過程，若否，那麼從位置i+1重新開始，但j仍然從當前位置考慮即可，原因上面已說明。這樣時間復雜度就成O(n)的了。
具體請參考代碼
[cpp] pair<int, int> find(const vector<int> &A)
{
int n = A.size();
if(n == 0)
throw new invalid_argument("Array's size can't be 0!");
vector<int> right_max_pos(n);
right_max_pos[n-1] = n-1;
for(int i = n-2; i >= 0; --i)
{
if(A[i] > A[right_max_pos[i+1]])
right_max_pos[i] = i;
else
right_max_pos[i] = right_max_pos[i+1];
}
int max_len = 0;
int target_i, target_j;
int i = 0, j = 0;
while(j < n)
{
j = right_max_pos[j];
if(A[j] >= A[i])
{
if(j-i+1 > max_len)
{
target_i = i;
target_j = j;
max_len = j-i+1;
}
++j;
}
else
++i;
}
return make_pair<int, int>(target_i, target_j);
}
pair<int, int> find(const vector<int> &A)
{
int n = A.size();
if(n == 0)
throw new invalid_argument("Array's size can't be 0!");
vector<int> right_max_pos(n);
right_max_pos[n-1] = n-1;
for(int i = n-2; i >= 0; --i)
{
if(A[i] > A[right_max_pos[i+1]])
right_max_pos[i] = i;
else
right_max_pos[i] = right_max_pos[i+1];
}
int max_len = 0;
int target_i, target_j;
int i = 0, j = 0;
while(j < n)
{
j = right_max_pos[j];
if(A[j] >= A[i])
{
if(j-i+1 > max_len)
{
target_i = i;
target_j = j;
max_len = j-i+1;
}
++j;
}
else
++i;
}
return make_pair<int, int>(target_i, target_j);
}
這裡簡單說一下測試方法，測試我們可以先測試最簡單的實現方案，這裡的第一種實現，因為這種實現簡單，出現錯誤的可能性小，測試起來簡單。測試時可以不考慮時間復雜度，只考慮正確性。然後我們使用此經過測試過的算法的輸入輸出去測試其他算法（對於結果）。
