tldr, O(n^2)
Вы можете использовать несколько графовых алгоритмов:
Каждая из ваших точек (скажем, p) может быть отображена как два узла (po и * 1008). *): 1o, 1c, 3o, 3c 5o, 5c, 9o, 9c, где o обозначает открытие, а c обозначает закрытие.
Поскольку вы рассматриваете пары
- , каждый открывающий узел может быть соединен с закрытием узел для стоимости, которую вы определили
- , каждый закрытый узел может быть подключен к открывающему узлу со стоимостью 0 (чтобы разрешить открытие новой пары)
, например: в вашем случае взвешенные ребра:
// user defined
w(1o, 3c) = 2
w(1o, 5c) = 4
w(3o, 5c) = 1
w(5o, 9c) = 3
// enable connection of pairs
w(1c, 1o) = 0
w(1c, 3o) = 0
w(1c, 5o) = 0
w(1c, 9o) = 0
w(3c, 3o) = 0
w(3c, 5o) = 0
w(3c, 9o) = 0
w(5c, 5o) = 0
w(5c, 9o) = 0
Обратите внимание, что ребро e (x, 9o) бесполезно, поскольку мы не можем создать пару с последней точкой в качестве первого элемента пары ...
К этим взвешенным ребрам мы можем добавить дополнительный закрывающий узел S, который подключен ко всем открывающим узлам
w(S, 1o) = 0
w(S, 3o) = 0
w(S, 5o) = 0
w(S, 9o) = 0
У нас есть DAG (график прямой ациклизации c), к которому мы хотим найти самый длинный путь к любому узлу из источника S.
Алгоритм должен быть в O (E + V) , где E - число ребер и V количество вершин
Что касается топологического упорядочения, точки p по возрастанию значения почти уже определяют его: p_c должно предшествовать p_o, так как мы можем иметь ребро (p_c, p_o)
Ниже код находится в O(n^2), с n количеством точек, так как для соединения пар нам нужно создать ребро от каждого закрывающего узла до следующих открывающих ( около n (n + 1) / 2)
//pseudocode: https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/
function longest(V, E) {
let max = -9000
const dist = V.reduce((acc, v)=>(acc[v] = -9000, acc), [])
dist[V[0]] = 0
V.forEach(u => {
E[u].forEach(([v, w]) => {
if (dist[v] < dist[u] + w) {
dist[v] = dist[u] + w
if (dist[v] > max) {
max = dist[v]
}
}
})
})
return max
}
function buildVE () {
const open = x => x+'o'
const close = x => x+'c'
const points = [0].concat([1, 3, 5, 9])
//close occurs before open because 5c can link to 5o
const V = [close(0)].concat(points.slice(1).flatMap(x => [close(x), open(x)]))
const E = {}
const addEdge = (a, b, w) => {
E[a] = E[a] || []
E[a].push([b, w])
}
addEdge(open(1), close(3), 2)
addEdge(open(1), close(5), 4)
addEdge(open(3), close(5), 1)
addEdge(open(5), close(9), 3)
for (let i = 0; i < points.length; ++i) {
for (let j = i; j < points.length; ++j) {
addEdge(close(points[i]), open(points[j]), 0)
}
}
const last = points[points.length-1]
E[open(last)] = []
E[close(last)] = []
return {V, E}
}
const {V, E} = buildVE()
console.log(longest(V, E))