最大权重递增子序列

Question

在最长上升子序列问题中，如果我们按权重更改长度，即每个元素A_i的长度为1，如果我们将其更改为W_i，我们该如何以O(NlogN)的时间复杂度来解决。

例如，对于一个包含8个元素的数组：

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

最大重量为110。

我在维基百科上找到了LIS的解决方案，但我无法修改它以解决这个问题。

- Anubhav Agarwal

---

请使用测试用例在HackerRank上解决此编程问题 - www.hackerrank.com/challenges/subsequence-weighting - rakesh sinha

Answer 1

然而，我们使用 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] 变化范围很大，可以进行 离散化。

- iloahz

---

什么是dp[i]？ 请问在线段树中会存储什么？谢谢。 - amahfouz

@amahfouz dp(i) 只是一个计算 f[i] 值的函数。在线段树中，索引（或范围）是 E 的值，更新单个插槽的值，在范围内查询最大值，这是典型的线段树。 - iloahz

谢谢回复。 - amahfouz

Answer 2

这是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)
}

可以随意添加记忆化 ;)

- Danil