Максимальная последовательность увеличения веса

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 в Википедии, но не могу изменить его, чтобы решить эту проблему.

Answer 1

Тем не менее, мы используем f[i] обозначает максимальное значение, которое мы можем получить, заканчивая последовательность с E[i].

Итак, обычно у нас есть for (int i = 1;i <= n;i++) f[i] = dp(i); и первоначально f[0] = 0; и E[0] = -INF;

Теперь мы вычислим f[i] в dp(i) в пределах O(log(N)).

в dp(i), мы найдем максимум f[j] с E[j] < E[i] для всех 0 <= j < 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.

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

Не стесняйтесь добавлять памятки;)