#3530

Maximum Profit from Valid Topological Order in DAG

international master · 1990 · lc hard +32 · 29.9% accepted · 58 likes · top 7%

Description

A DAG with n nodes and edge list edges[i] = [ui, vi] is given. Each node has a score. Process nodes in some valid topological order; node at position p (1-indexed) contributes score * p to the profit.

Return the maximum achievable profit over all valid topological orderings.

Code

1

2

3

class Solution:
    def maxProfit(self, n: int, edges: List[List[int]], score: List[int]) -> int:

class Solution:
    def maxProfit(self, n: int, edges: List[List[int]], score: List[int]) -> int: