最大重量遞增子

在Longest Increasing Subsequence Problem如果我們重量改變長度即每個元素A _我的長度爲1，如果我們將其更改至W _我我們怎樣才能做到這一點在O（NlogN）。最大重量遞增子

對於實施例對於8個元素

Elements 1 2 3 4 1 2 3 4 
Weights 10 20 30 40 15 15 15 50

的最大重量爲110

我發現維基百科上的LIS解決方案，但我不能修改它來解決這個問題的陣列。

來源

2012-01-09 Anubhav Agarwal

儘管如此，我們仍然使用f[i]表示我們可以用E[i]以序列結束時獲得的最大值。

所以一般我們for (int i = 1;i <= n;i++) f[i] = dp(i);並初步f[0] = 0;和E[0] = -INF;

現在，我們將在dp(i)內O(log(N))計算f[i]。

in dp(i)，對於所有的0 <= j < i，我們將找到最大f[j]和E[j] < E[i]。在這裏我們可以保持Segment Tree。

所以dp(i) = find_max(1,E[i]-1) + W[i]（這需要O(log)），並且對於已經計算的每個f [i]，update(E[i],f[i])。

所以整個算法需要(O(NlogN))。

提示：如果E[i]在很大的範圍內變化，它可以是Discretization ed。

來源

2012-01-09 08:52:11 Topro

什麼是DP [I]？你可以請什麼將存儲在段樹？謝謝。 – amahfouz 2015-07-07 09:40:16

@amahfouz dp（i）只是計算f [i]值的函數。在分段樹中，索引（或範圍）是E的值，更新單個槽處的值，查詢範圍中的最大值，即典型分段樹。 – Topro 2015-07-26 07:32:33

感謝您的回覆。 – amahfouz 2015-07-27 14:19:34

這裏是純粹的遞歸實施SWIFT：

// input is Array of (a,w), where a is element and w is weight 

func lisw(input: [(Int, Int)], index:Int = 0, largestA:Int? = nil)->Int{ 
     guard index < input.count else { return 0 } 

     let (a,w) = input[index] 

     if a <= largestA { 
      return lisw(input: input, index: index + 1, largestA: largestA) 
     } 

     let without_me = lisw(input: input, index: index + 1, largestA: largestA == nil ? a : largestA) 
     let with_me = lisw(input: input, index: index + 1, largestA: a) + w 

     return max(without_me,with_me) 
}

隨意添加記憶化;）

來源

2016-09-09 19:49:04 Danil

最大重量遞增子

回答

相關問題