1626. Best Team with no Conflicts - Explanation

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        pairs = [[scores[i], ages[i]] for i in range(len(scores))]
        pairs.sort()
        dp = {}

        def dfs(i, j):
            if i == len(pairs):
                return 0
            if (i, j) in dp:
                return dp[(i, j)]

            mScore, mAge = pairs[j] if j >= 0 else [0, 0]
            score, age = pairs[i]
            res = 0
            if not (score > mScore and age < mAge):
                res = dfs(i + 1, i) + score  # add score
            dp[(i, j)] = max(res, dfs(i + 1, j))  # skip score
            return dp[(i, j)]

        return dfs(0, -1)

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        pairs = [[scores[i], ages[i]] for i in range(len(scores))]
        pairs.sort()
        dp = [pairs[i][0] for i in range(len(pairs))]

        for i in range(len(pairs)):
            mScore, mAge = pairs[i]
            for j in range(i):
                score, age = pairs[j]
                if mAge >= age:
                    dp[i] = max(dp[i], mScore + dp[j])

        return max(dp)

class SegmentTree:
    def __init__(self, N):
        self.n = N
        while (self.n & (self.n - 1)) != 0:
            self.n += 1
        self.build()

    def build(self):
        self.tree = [0] * (2 * self.n)

    def update(self, i, val):
        pos = self.n + i
        self.tree[pos] = max(self.tree[pos], val)
        pos >>= 1
        while pos >= 1:
            self.tree[pos] = max(self.tree[pos << 1], self.tree[pos << 1 | 1])
            pos >>= 1

    def query(self, l, r):
        res = 0
        l += self.n
        r += self.n + 1
        while l < r:
            if l & 1:
                res = max(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res

class Solution:
    def bestTeamScore(self, scores: list[int], ages: list[int]) -> int:
        pairs = [[scores[i], ages[i]] for i in range(len(scores))]
        pairs.sort()

        dp = [pairs[i][0] for i in range(len(pairs))]
        unique_ages = sorted({ age for _, age in pairs })
        ageId = { val: idx for idx, val in enumerate(unique_ages) }

        segtree = SegmentTree(len(pairs))

        res = 0
        for i in range(len(pairs)):
            mScore, mAge = pairs[i]
            idx = ageId[mAge]
            j = segtree.query(0, idx)
            dp[i] = j + mScore
            segtree.update(idx, dp[i])
            res = max(res, dp[i])

        return res