Maximum Profit from Valid Topological Order in DAG
HardPrompt
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 fromuitovi.0 <= ui, vi < nui != vi- The input graph is guaranteed to be a DAG.
- There are no duplicate edges.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach generates every possible ordering (permutation) of the n nodes. For each permutation, it first checks if the ordering is a valid topological sort by verifying the precedence constraints for all edges. If it is a valid topological sort, it calculates the total profit for that ordering. The maximum profit found across all valid topological orderings is the result.
Algorithm
- Generate all
n!permutations of the nodes0, 1, ..., n-1. - For each permutation
P:- Check if
Pis a valid topological sort by verifying that for every edgeu -> v,uappears beforevinP. - If
Pis valid, calculate its profit:Σ(score[P[i]] * (i+1)). - Update the overall maximum profit.
- Check if
- Return the maximum profit.
Walkthrough
The algorithm proceeds as follows:
- Generate all
n!permutations of the nodes0, 1, ..., n-1. - For each permutation
P: a. Check ifPis a valid topological sort. To do this, we can create a mapping from each node to its position inP. Then, for every edgeu -> vin the graph, we check ifposition[u] < position[v]. If this condition holds for all edges, the permutation represents a valid topological order. b. IfPis valid, calculate its profit. The profit is the sum ofscore[P[i]] * (i + 1)forifrom 0 ton-1. c. Keep track of the maximum profit found so far. - After checking all permutations, return the overall maximum profit.
This is a naive approach that explores the entire search space of permutations, most of which will be invalid for a typical DAG.
import java.util.ArrayList;import java.util.Collections; class Solution { long maxProfit = 0; public long maximumProfit(int n, int[][] edges, int[] score) { ArrayList<Integer> nodes = new ArrayList<>(); for (int i = 0; i < n; i++) { nodes.add(i); } permute(nodes, 0, n, edges, score); return maxProfit; } private void permute(ArrayList<Integer> arr, int k, int n, int[][] edges, int[] score) { if (k == arr.size()) { if (isValidTopologicalSort(arr, n, edges)) { calculateProfit(arr, score); } return; } for (int i = k; i < arr.size(); i++) { Collections.swap(arr, i, k); permute(arr, k + 1, n, edges, score); Collections.swap(arr, k, i); } } private boolean isValidTopologicalSort(ArrayList<Integer> order, int n, int[][] edges) { int[] pos = new int[n]; for (int i = 0; i < n; i++) { pos[order.get(i)] = i; } for (int[] edge : edges) { if (pos[edge[0]] > pos[edge[1]]) { return false; } } return true; } private void calculateProfit(ArrayList<Integer> order, int[] score) { long currentProfit = 0; for (int i = 0; i < order.size(); i++) { currentProfit += (long) score[order.get(i)] * (i + 1); } maxProfit = Math.max(maxProfit, currentProfit); }}Complexity
Time
O(n! * E), where `n` is the number of nodes and `E` is the number of edges. Generating `n!` permutations and checking each one for validity (which takes O(E) time) is computationally prohibitive.
Space
O(n) for storing the permutation and recursion stack.
Trade-offs
Pros
Conceptually simple and straightforward to understand.
Cons
Extremely inefficient due to the factorial time complexity.
Not feasible for the given constraints (
nup to 22).
This approach uses dynamic programming with bitmasking to build a valid topological order step by step. A bitmask mask represents the set of nodes that have already been placed in the ordering. The DP state dp[mask] stores the maximum profit achievable by arranging the nodes in mask into a valid partial topological order.
Algorithm
- Pre-calculate a predecessor mask for each node.
pred_mask[i]is a bitmask where thej-th bit is 1 ifj -> iis an edge. - Initialize a DP array
dpof size2^n.dp[mask]will store the max profit for the nodes inmask. Setdp[0] = 0and others to a value indicating they are not yet computed (e.g., -1). - Iterate through masks from 1 to
(1 << n) - 1. - For each
mask, letk = popcount(mask). - Iterate through each node
ufrom 0 ton-1. - If
uis inmask:- Let
prev_mask = mask \ {u}. - Check if all predecessors of
uare inprev_maskusing(pred_mask[u] & prev_mask) == pred_mask[u]. - If the condition holds and
dp[prev_mask]is a valid state, updatedp[mask]withmax(dp[mask], dp[prev_mask] + score[u] * k).
- Let
- The final answer is
dp[(1 << n) - 1].
Walkthrough
We define dp[mask] as the maximum profit for a valid topological ordering of the nodes represented by the bitmask mask. The positions used for this subproblem are from 1 to k, where k is the number of set bits in mask (popcount(mask)).
The state transition is formulated by considering which node u (from the set mask) could have been placed at the last position, k. A node u can be placed at position k only if all of its predecessors are already present in the set of previously placed nodes, represented by mask \ {u}.
The recurrence relation is:
dp[mask] = max(dp[mask \ {u}] + score[u] * k)
This maximum is taken over all nodes u in mask that satisfy the precedence constraints.
import java.util.Arrays; class Solution { public long maximumProfit(int n, int[][] edges, int[] score) { int[] predMask = new int[n]; for (int[] edge : edges) { predMask[edge[1]] |= (1 << edge[0]); } long[] dp = new long[1 << n]; Arrays.fill(dp, -1); dp[0] = 0; for (int mask = 1; mask < (1 << n); mask++) { int k = Integer.bitCount(mask); for (int u = 0; u < n; u++) { if ((mask & (1 << u)) != 0) { // If u is in the current set int prevMask = mask ^ (1 << u); // Check if all predecessors of u are in the previous set if ((predMask[u] & prevMask) == predMask[u]) { if (dp[prevMask] != -1) { long currentProfit = dp[prevMask] + (long) score[u] * k; if (dp[mask] == -1 || currentProfit > dp[mask]) { dp[mask] = currentProfit; } } } } } } return dp[(1 << n) - 1]; }}Complexity
Time
O(n * 2^n). We iterate through `2^n` masks, and for each mask, we perform an inner loop of `n` iterations.
Space
O(2^n) to store the DP table `dp`.
Trade-offs
Pros
Guaranteed to find the optimal solution.
Much faster than the brute-force approach.
Feasible for the given constraint of
n <= 22.
Cons
The exponential time and space complexity make it impractical for larger values of
n.Can be complex to understand and implement correctly.
This is the most efficient approach. It's based on the observation that to maximize the total profit, we should assign smaller positions (multipliers) to nodes with smaller scores, and larger positions to nodes with larger scores. This can be achieved with a greedy strategy. We adapt Kahn's algorithm for topological sorting. At each step, among all nodes that are ready to be processed (i.e., all their predecessors have been processed), we greedily pick the one with the smallest score.
Algorithm
- Build an adjacency list and an in-degree array for the graph from the
edges. - Initialize a min-priority queue that orders nodes by their scores in ascending order.
- Add all nodes with an initial in-degree of 0 to the priority queue.
- Initialize
totalProfit = 0andposition = 1. - While the priority queue is not empty:
- Extract the node
uwith the minimum score. - Add its profit contribution:
totalProfit += score[u] * position. - Increment
position. - For each neighbor
vofu:- Decrement the in-degree of
v. - If
v's in-degree becomes 0, add it to the priority queue.
- Decrement the in-degree of
- Extract the node
- Return
totalProfit.
Walkthrough
The optimality of this greedy strategy can be proven with an exchange argument. Suppose at some step k, we have two available nodes u and v where score[u] < score[v]. If we pick u at position k and v at a later position k+1, their contribution to the profit is score[u]*k + score[v]*(k+1). If we swap them, the contribution becomes score[v]*k + score[u]*(k+1). The difference is (score[u]*k + score[v]*(k+1)) - (score[v]*k + score[u]*(k+1)) = score[v] - score[u] > 0. Thus, placing the smaller-score node u earlier always leads to a better or equal total profit. This logic extends to any set of available nodes, proving the greedy choice is optimal.
The implementation uses a min-priority queue to efficiently retrieve the available node with the minimum score at each step.
import java.util.*; class Solution { public long maximumProfit(int n, int[][] edges, int[] score) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } int[] inDegree = new int[n]; for (int[] edge : edges) { adj.get(edge[0]).add(edge[1]); inDegree[edge[1]]++; } // Priority queue stores pairs of [score, node_index] // It's a min-heap based on score. PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); for (int i = 0; i < n; i++) { if (inDegree[i] == 0) { pq.offer(new int[]{score[i], i}); } } long totalProfit = 0; long position = 1; while (!pq.isEmpty()) { int[] current = pq.poll(); int u = current[1]; totalProfit += (long) score[u] * position; position++; for (int v : adj.get(u)) { inDegree[v]--; if (inDegree[v] == 0) { pq.offer(new int[]{score[v], v}); } } } return totalProfit; }}Complexity
Time
O((n + E) log n). Building the graph takes O(n + E). The main loop involves `n` extractions (O(n log n)) and `E` potential insertions (O(E log n)) into the priority queue.
Space
O(n + E) for storing the adjacency list, in-degree array, and the priority queue.
Trade-offs
Pros
Highly efficient and optimal for this problem.
Relatively simple to implement using standard graph algorithms.
Scales well for much larger
nandEthan the other approaches.
Cons
The proof of optimality, while correct, is based on an exchange argument which might not be immediately obvious.
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.