Watch 4 video solutions for Maximum Profit from Valid Topological Order in DAG, a hard level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by Romain Lhotte has 277 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a Directed Acyclic Graph (DAG) with n nodes labeled from 0 to n - 1, represented by a 2D array edges, where edges[i] = [ui, vi] indicates a directed edge from node ui to vi. Each node has an associated score given in an array score, where score[i] represents the score of node i.
You must process the nodes in a valid topological order. Each node is assigned a 1-based position in the processing order.
The profit is calculated by summing up the product of each node's score and its position in the ordering.
Return the maximum possible profit achievable with an optimal topological order.
A topological order of a DAG is a linear ordering of its nodes such that for every directed edge u → v, node u comes before v in the ordering.
Example 1:
Input: n = 2, edges = [[0,1]], score = [2,3]
Output: 8
Explanation:
Node 1 depends on node 0, so a valid order is [0, 1].
| Node | Processing Order | Score | Multiplier | Profit Calculation |
|---|---|---|---|---|
| 0 | 1st | 2 | 1 | 2 × 1 = 2 |
| 1 | 2nd | 3 | 2 | 3 × 2 = 6 |
The maximum total profit achievable over all valid topological orders is 2 + 6 = 8.
Example 2:
Input: n = 3, edges = [[0,1],[0,2]], score = [1,6,3]
Output: 25
Explanation:
Nodes 1 and 2 depend on node 0, so the most optimal valid order is [0, 2, 1].
| Node | Processing Order | Score | Multiplier | Profit Calculation |
|---|---|---|---|---|
| 0 | 1st | 1 | 1 | 1 × 1 = 1 |
| 2 | 2nd | 3 | 2 | 3 × 2 = 6 |
| 1 | 3rd | 6 | 3 | 6 × 3 = 18 |
The maximum total profit achievable over all valid topological orders is 1 + 6 + 18 = 25.
Constraints:
1 <= n == score.length <= 221 <= score[i] <= 1050 <= edges.length <= n * (n - 1) / 2edges[i] == [ui, vi] denotes a directed edge from ui to vi.0 <= ui, vi < nui != viProblem Overview: You are given a directed acyclic graph (DAG) and a profit rule based on the order in which nodes appear in a valid topological ordering. The goal is to choose a topological order that maximizes the total profit while respecting all prerequisite edges.
Approach 1: Enumerate All Topological Orders (Brute Force) (Time: O(n! + E), Space: O(n + E))
The most direct idea is to generate every valid topological ordering of the DAG and compute the profit for each order. Use backtracking with an indegree array: repeatedly choose any node whose indegree is zero, place it in the current order, update neighbors, and recurse. After constructing a full order, evaluate the profit based on each node’s position. This approach demonstrates how topological ordering works but becomes infeasible quickly because the number of valid orders can approach n! in sparse DAGs.
Approach 2: Bitmask Dynamic Programming with Prerequisite Masks (Time: O(n * 2^n), Space: O(2^n))
A more efficient strategy treats the problem as a state transition over subsets of nodes. Precompute a prerequisite bitmask for every node, where bit j indicates that node j must appear before it. Define dp[mask] as the maximum profit achievable when the set of nodes already placed in the order equals mask. The current position in the order is k = popcount(mask). From this state, iterate through all nodes not in mask. A node can be chosen next only if all its prerequisites are already in mask (i.e., (mask & prereq[i]) == prereq[i]). Place that node next, compute the profit contributed at position k, and update dp[mask | (1 << i)]. This converts the exponential permutation search into a manageable subset DP.
The key observation is that the validity of a partial order depends only on which nodes have already been placed, not their exact sequence. Encoding the chosen nodes in a bitmask lets you verify prerequisites using fast bit operations. This technique frequently appears in problems combining dynamic programming, bitmask, and topological sort constraints.
Recommended for interviews: The bitmask DP approach is the expected solution. Brute force enumeration shows you understand topological ordering, but interviewers usually look for the subset DP optimization that reduces the search space from factorial to O(n * 2^n). It demonstrates comfort with DAG constraints, state compression, and graph-based DP.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking over all topological orders | O(n! + E) | O(n + E) | Useful for understanding the problem or when the graph is extremely small |
| Bitmask DP with prerequisite masks | O(n * 2^n) | O(2^n) | Optimal for n ≤ ~20 where subset DP efficiently enforces topological constraints |