尋找A的最大價值[J] + - A [I]

Question

我下週有總決賽，我正在努力學習舊筆記和家庭作業/考試。在我的第二個作業中，我有一個問題，我錯了，我只是不確定究竟該做什麼。問題如下：

設計高效的算法，採用一組正數「a」，並確定： a。 a [j] + a [i]的最大值，其中j>或= to i。 b。 a [j] - a [i]的最大值，其中j>或= to i。

我不想要實際的代碼，只是一些僞代碼和它的運行時間。

我想會的工作：

找到第一，第二和第三最大值和最小值。 然後做： a。第一個最大a（j）+第二個最大a（i），對於j> = i。 b。第一個最大a（j） - 第一個最小a（i），對於j> = i

然後，如果上述條件失敗，只需重複第二個最大值，最小值。

我不知道爲什麼我不能把頭繞在這裏。我知道j可以等於i，所以我的答案會產生a部分的錯誤結果。對於b部分來說，假設我有一個數組[89 | 90 | 1 | 2 | 3 | 4 | 5]，它將變爲90 - 1 = 89，但它應該是5 - 1 = 4。我甚至沒有嘗試考慮到運行時間，因爲那一部分是錯誤的。

任何幫助或提示將是偉大的。謝謝！

Answer 1

a。 a [j] + a [i]是直接的，它只是2 *最大，因爲j可以等於我可以在O(N)

b。 a [j] - a [i]在這種情況下，我們需要動態編程來獲取它的O（N）。下面是一個方法來做到這一點在O（N）： -

建立一個數組，使得MAX [i]表示在子陣列A [1到n]

max[n] = a[n]   
for(i=n-1;i>=1;i--) 
    max[i] = maximum(max[i+1],a[i]); 

然後找到最大值最大元件(max[i]-a[i])對於所有我將是你的max a[j]-a[i]。剛剛意識到不需要維護數組max []，只需使用前一個數值就可以計算max [i] - a [i]，同時評估max [i]。

Answer 2

a。到最大值a [i] + a [j]是要找到數組中的最大值和第二大值，它很簡單，時間複雜度爲O（N）。

b。爲了最大化[j] -a [i]（j> = i），對於每個j，可能的最優解將是a [j] - j之前的最小值，所以你只需要保持這個值並更新最好的解決方案

mmin = a[0]; 
ans = 0; 
for (int j = 0; j < length(a); ++j){ 
    mmin = min(a[j], mmin); 
    ans = max(ans, a[j] - mmin); 
} 
return ans; 

它也是O（N）。