如何找到給定數組的最大跨度？

Question

我想解決的問題如下：我想找到一個給定的數組中的數字的最大跨度給定數組A包含正整數和負整數返回最大（A [j] - A [ I]），使得1 < = I <Ĵ< = n，並且我想出了針對此問題以下nlogn時間算法 - ：

1. 找到陣列的n階統計量的索引讓它成爲「i」
2. 找到數組的第一條統計量的索引讓它成爲「j」
3. 如果i> j，則返回差異，因爲我們發現差異在數組的最大元素和最小元素之間，因此只是終止返回差異。
4. 如果j> i，然後將數組分成兩半，並通過調用此函數在兩半中找到最大跨度，即A [1 .... i]和A [i + 1 ...... n]算法是遞歸的，情況是當算法找到這樣的一對i，j它返回那些對之間的差別，否則它保持遞歸併最終終止。
5. 回報最大{子陣列1的max_span，subarray2的max_span}

該算法是O（nlogn），但我不知道，如果它的正確與否。

Answer 1

這是一個O（n）算法。

1. 建立一個數組Max Max其中Max [i]是k> = i時A [k]的最大值。這可以在O（n）時間通過向後迭代A完成。
2. 構建一個數組最小值其中Min [i]是A [k]的最小值，代表k < = i。再次O（n）。
3. 遍歷Max和Min以找到使Max [i] -Min [i]最大化的索引i。還有O（n）。
4. Return（Min [i]，Max [i]）。

在編輯：有一個角落的情況下，其中陣列是相反的排序順序，在這種情況下，最大[I] =最小值[I] = A [1]對於所有的i。這可以在O（n）時間內檢測到，在這種情況下，您只需返回使A [i + 1] -A [i]（將爲負數）最大的相鄰元素對。

Answer 2

@mrip解決方案的複雜性是時間O（n）和空間O（n）。這是正確的，但是隻有O（1）空間複雜度足以解決這個問題。

int min=a[0],ans=0; 
for (int i=1;i<n;i++) 
    if (a[i]<min) min=a[i]; 
    else ans=max(ans,a[i]-min); 
return ans;