增加比例最高

Question

比方說我們有以下組表示值的數字隨着時間的推移

1 2 3 10 1 20 40 60 

現在我正在尋找一種算法來找到一個時間的增加比例最高到另一個。在上述情況下，答案將是一對（1，60），增加了6000％。

到目前爲止，我能想到的最好的算法是強力方法。我們可以考慮使用一系列迭代的所有可能的對：

第一次迭代：

1-2 1-3 1-10 .. 1-60 

第二迭代

2-3 2-10 2-1 ... 2-60 

（等）

這有複雜度爲O（N ）。

我也一直在想另一種方法。找出所有嚴格遞增的序列，並確定那些嚴格遞增的序列中只有增加的百分比。

是否有其他想法打擊你們？如果我的想法錯誤，請糾正我的錯誤！

Answer 1

我可能誤解了這個問題，但似乎所有你想要的是最大和最小的數字，因爲那些是兩個重要的數字。

while true: 
    indexOfMax = max(list) 
    indexOfMin = min(list) 
    list.remove(indexOfMax) 
    list.remove(indexOfMin) 
    if(indexOfmax < indexOfMin) 
     contine 
    else if(indexOfMax == indexOfMin) 
     return -1 
    else 
     SUCCESS 

Answer 2

據我所知（你沒有在你的評論中糾正我），你想要最大限度地爲a[i]/a[j]所有j <= i。如果這是正確的，那麼對於每個i，我們只需要知道它之前的最小值。

int current_min = INFINITY; 
double max_increase = 0; 
for (int i = 0; i < n; ++i) { 
    current_min = min(current_min, a[i]); 
    max_increase = max(max_increase, a[i]/min); 
} 

Answer 3

因此，您只是想比較每個數字，並從第二個數字到第一個數字看哪個對的比率最高？只需迭代兩個循環（一個用i = 0到n，而一個用j = i + 1到n的內循環）就會給你O（n^2）。我想這實際上是你原來的解決方案，但你錯誤地說複雜性是O（n^3）。這是n^2。

雖然你可以去O（n日誌n）。把你的清單，成爲一個列表，其中每個元素是一對（索引，值）。然後按照該對中的第二個元素進行排序。然後在列表中有兩個指針，一個來自左邊（0到n-1），另一個來自右邊（n-1到0）。找到第一對元素，使左元素的原始索引小於右元素的原始索引。完成。

1 2 3 10 1 20 40 60 
becomes 
(1,0) (2,1) (3,2) (10,3) (1, 4) (20, 5) (40, 6) (60,7) 
becomes 
(1,0) (1,4) (2,1) (3,2) (10,3) (20,5) (40,6) (60,7) 

所以你的答案是60/1，從指數0到7索引

如果這是不是你要找什麼，它會幫助，如果你說了什麼，正確答案是你的例子數字。

Answer 4

如果我正確理解你的問題，你正在尋找具有最高比率A [j]/A [i]的數組中的兩個指數（i，j）。如果是這樣，那麼你可以將它減少到this related problem，它會要求你找到指數（i，j），使得A [j] - A [i]儘可能大。這個問題有一個非常快的O（n） - 時間，O（1） - 空間算法，可以適應這個問題。直覺就是解決由數組的第一個元素組成的數組，然後是前兩個元素，然後是前三個元素等的問題。一旦你解決了數組中前n個元素的問題，你有問題的全面解決方案。

讓我們考慮如何做到這一點。最初，當您考慮數組的第一個元素時，通過比較元素與其自身，可以得到的最佳百分比增量爲0％。現在，假設（歸納地）你已經解決了前k個數組元素的問題，並想知道當你看下一個數組元素時會發生什麼。發生這種情況時，兩個條件之一成立。首先，前k個元素的最大百分比增加也可能是第一個（k + 1）元素的最大百分比增加。例如，如果第（k + 1）個st數組元素是一個非常小的數字，那麼您很可能無法從前k個元素中的某個值增加到該值。其次，最大百分比增加可能是從前k個元素中的一個到第（k + 1）個st元素。如果是這種情況，則最高百分比增加將從最初的k個元素到第（k + 1）個元素。

結合這兩種情況，我們得到了最好的百分比增幅比前k + 1個元素是最大的

• 第k個元素的增加比例最高，或
• 增加的百分比從最小的第k個元素到第（k + 1）個st元素。

您可以通過遍歷數組元素遍歷數據元素來實現此操作，以跟蹤兩個值 - 您迄今爲止看到的最小值和最大化增加百分比的對。舉個例子，對於

1 2 3 10 1 20 40 60 

你原來的例子陣列算法將這樣的工作：

 1  2  3  10  1  20  40  60 
min  1  1  1  1  1   1  1  1 
best  (1,1) (1, 2) (1, 3) (1, 10) (1, 10) (1, 20) (1, 40) (1, 60) 

和你輸出（1，60）爲增加比例最高。在不同的陣列，像這樣的：

3 1 4 2 5 

然後算法將描繪出這樣的：分鐘3 1 1 1 1 最好（3,3）（3,3） （1,4）（1,4）（1,5）

你會輸出（1,5）。

這整個算法只使用O（1）空間，並運行在O（n）時間，這是一個非常好的解決問題的方法。

或者，您可以考慮通過取數組中所有值的對數，將此問題直接減少到最大單次銷售利潤問題。在這種情況下，如果找到log A [j] - log A [i]被最大化的一對值，則這是等價的（使用對數的性質）來找到一對值，其中log（A [j]/A [i]）被最大化。由於對數函數單調增加，這意味着您已經找到了一對值，其中A [j]/A [i]按照預期最大化。