在最长上升子序列问题中,如果我们按权重更改长度,即每个元素Ai的长度为1,如果我们将其更改为Wi,我们该如何以O(NlogN)的时间复杂度来解决。
例如,对于一个包含8个元素的数组:
Elements 1 2 3 4 1 2 3 4
Weights 10 20 30 40 15 15 15 50
最大重量为110。
我在维基百科上找到了LIS的解决方案,但我无法修改它以解决这个问题。
在最长上升子序列问题中,如果我们按权重更改长度,即每个元素Ai的长度为1,如果我们将其更改为Wi,我们该如何以O(NlogN)的时间复杂度来解决。
例如,对于一个包含8个元素的数组:
Elements 1 2 3 4 1 2 3 4
Weights 10 20 30 40 15 15 15 50
最大重量为110。
我在维基百科上找到了LIS的解决方案,但我无法修改它以解决这个问题。
然而,我们使用 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]
。
在 dp(i)
中,我们将在所有 0 <= j < i
的情况下找到满足 E[j] < E[i]
的最大 f[j]
。在这里,我们可以维护一个 线段树
。
因此,dp(i) = find_max(1,E[i]-1) + W[i]
(这需要 O(log)
),对于已经计算出来的每个 f[i]
,都要 update(E[i],f[i])
。
整个算法需要 (O(NlogN))
的时间。
提示:如果 E[i]
变化范围很大,可以进行 离散化
。
这是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)
}
可以随意添加记忆化 ;)