Skip to main content
Talentd

Maximum Profit from Valid Topological Order in DAG - Solution & Explanation

HardArrayDynamic ProgrammingBit ManipulationGraph4 min read
Practice this problem

Problem Statement

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 <= 22
  • 1 <= score[i] <= 105
  • 0 <= edges.length <= n * (n - 1) / 2
  • edges[i] == [ui, vi] denotes a directed edge from ui to vi.
  • 0 <= ui, vi < n
  • ui != vi
  • The input graph is guaranteed to be a DAG.
  • There are no duplicate edges.

Approach Overview

Problem 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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking over all topological ordersO(n! + E)O(n + E)Useful for understanding the problem or when the graph is extremely small
Bitmask DP with prerequisite masksO(n * 2^n)O(2^n)Optimal for n ≤ ~20 where subset DP efficiently enforces topological constraints

Video Solution

[English] 3530. Maximum Profit from Valid Topological Order in DAG - Q4 Biweekly 155 [Leetcode Hard] • Romain Lhotte • 312 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Maximum Profit from Valid Topological Order in DAG easy or hard?
This problem is considered hard because it combines multiple advanced ideas: DAG constraints, topological ordering, and bitmask dynamic programming. Recognizing that the state can be represented by a subset of completed nodes is the key insight that unlocks the O(n * 2^n) solution.
Maximum Profit from Valid Topological Order in DAG Python/Java solution
Most implementations build a prerequisite bitmask for each node and run DP over all subsets. The same logic translates cleanly across Python, Java, C++, and Go: iterate masks from 0 to (1<<n)-1, find available nodes whose prerequisites are satisfied, and update the DP state with the profit gained at the current position.
How to solve Maximum Profit from Valid Topological Order in DAG in O(n * 2^n)?
Precompute a prerequisite bitmask for every node in the DAG. Use DP where dp[mask] stores the best profit after placing nodes represented by mask. For each state, iterate over nodes not yet used and check whether their prerequisite mask is satisfied. If valid, place the node next and update the next DP state.
What is the best approach for Maximum Profit from Valid Topological Order in DAG?
The most effective approach is bitmask dynamic programming over subsets. Each DP state represents the set of nodes already placed in the topological order. From that state, you try adding any node whose prerequisites are already satisfied. This reduces the search space from factorial permutations to O(n * 2^n) transitions.
Is Maximum Profit from Valid Topological Order in DAG asked at Google/Amazon/Meta?
Problems combining topological ordering with dynamic programming or bitmask state compression appear frequently in interviews at companies like Google, Amazon, and Meta. They test graph reasoning, DAG constraints, and the ability to optimize exponential search using DP over subsets.
What data structure is used in Maximum Profit from Valid Topological Order in DAG?
The solution uses adjacency lists or prerequisite masks to represent the DAG, along with a DP array indexed by bitmask states. Bit manipulation allows fast checks to verify whether all prerequisites of a node are already included in the current subset.
What is the time complexity of Maximum Profit from Valid Topological Order in DAG?
The optimal solution runs in O(n * 2^n) time with O(2^n) space. Each bitmask represents a subset of nodes already placed in the order, and for each state you try adding up to n nodes whose prerequisites are satisfied.

Ready to solve this problem?

Practice Maximum Profit from Valid Topological Order in DAG with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays