LeetCode Problem 3530

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Graph Theory, Topological Sort, Bitmask

Solution

Problem Understanding

The problem requires computing the maximum possible profit achievable by processing nodes of a Directed Acyclic Graph (DAG) in a valid topological order. Each node has a score, and the profit contribution of a node is its score multiplied by its position in the processing order (1-based). The goal is to determine an ordering of the nodes that respects all DAG dependencies and maximizes the total profit.

The input consists of three parts: n, the number of nodes; edges, a list of directed edges defining the DAG; and score, an array of integers representing each node's score. The output is a single integer, the maximum achievable profit.

Constraints reveal that n can be at most 22, which is small enough to allow bitmask dynamic programming over subsets of nodes. The DAG guarantee ensures there are no cycles, which simplifies topological ordering. The score range is large (up to 10^5), so correctness requires careful ordering to maximize the weighted sum.

Important edge cases include a single-node DAG, a DAG with multiple independent nodes, and DAGs where many nodes depend on a single node or vice versa. The graph is guaranteed acyclic, so topological sorting is always possible.

Approaches

A brute-force approach would enumerate all valid topological orders, compute their profits, and return the maximum. This involves generating permutations constrained by edges, which is factorial in n and infeasible for n = 22.

The key insight for an optimal solution is to use dynamic programming over subsets of nodes (bitmask DP). For each subset of nodes, we track the maximum profit achievable by processing exactly those nodes. At each step, we can only add nodes whose dependencies are already in the subset. By iterating over all valid subsets and updating profits incrementally, we can efficiently compute the maximum profit.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Enumerates all valid topological orders; infeasible for n = 22
Bitmask DP	O(n * 2^n)	O(2^n)	Uses DP over subsets to choose valid next nodes and maximize profit

Algorithm Walkthrough

1. Construct an adjacency list from the edges array for easy dependency checking. Also, compute a bitmask pre[i] for each node i representing the set of nodes that must appear before i.
2. Initialize a DP array dp of size 2^n with all entries as -1 except dp[0] = 0. Here, dp[mask] will store the maximum profit achievable by processing nodes in the subset represented by mask.
3. Iterate over all possible subsets of nodes represented by mask from 0 to 2^n - 1.
4. For each node i not in mask, check if all its prerequisites are in mask using the bitmask pre[i]. If true, calculate the next mask mask | (1 << i) and update dp[next_mask] as the maximum of its current value or dp[mask] + score[i] * (number_of_set_bits(mask) + 1).
5. After processing all subsets, dp[(1 << n) - 1] contains the maximum profit achievable by processing all nodes.

Why it works: The DP ensures that at every subset, we consider all valid nodes that can be appended to the current order, respecting the DAG dependencies. The bitmask tracks exactly which nodes are used, ensuring no invalid topological order is counted. This problem asks us to construct a valid topological ordering of a Directed Acyclic Graph (DAG) in a way that maximizes a weighted sum of node scores based on their positions in the ordering.

We are given a DAG with n nodes labeled from 0 to n - 1. Each directed edge u → v enforces a constraint that node u must appear before node v in any valid ordering. Each node i has a numeric value score[i]. Once we choose a valid topological order, each node is assigned a 1-based position in that order. The total profit is computed as the sum over all nodes of:

score[i] * position[i]

The task is to find the maximum possible profit among all valid topological orderings.

The constraints are critical: n ≤ 22, which strongly indicates an exponential algorithm with bitmask dynamic programming is intended. A naive factorial exploration of all topological orders is impossible, but 2^n state DP is feasible.

The input guarantees the graph is a DAG, meaning at least one valid topological ordering always exists. Edges may be sparse or dense.

Important edge cases include graphs with no edges (any permutation is valid), chains (fully constrained ordering), and nodes with shared dependencies that restrict ordering heavily.

Approaches

The brute-force approach is to enumerate all valid topological orders of the DAG and compute the profit for each ordering. This can be done via backtracking with indegree tracking or DFS with visited states. While correct, this approach explores all permutations consistent with constraints, leading to factorial complexity in the worst case.

The optimal solution uses bitmask dynamic programming. The key insight is that the only thing that matters for future decisions is which nodes have already been placed, not the exact order itself. Once we know the subset of selected nodes, we also know the next position index implicitly. For a node to be eligible next, all its prerequisites must already be included in the current subset. This transforms the problem into a subset DP where each state represents a partial topological ordering.

We precompute prerequisite masks for each node and then build a DP over subsets, trying to place valid next nodes and accumulating profit based on the current position.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Enumerates all valid topological orders via backtracking
Optimal (Bitmask DP)	O(n · 2^n)	O(2^n + n^2)	DP over subsets with prerequisite constraints

Algorithm Walkthrough

We define a bitmask DP where each state represents which nodes have already been placed in the ordering.

1. We represent each subset of nodes using a bitmask of size n. If bit i is set, node i is already placed in the ordering. This compact representation allows us to efficiently track all partial solutions.
2. For each node, we compute a prerequisite bitmask. If there is an edge u → v, then u is added to prereq[v]. This allows us to quickly check whether a node is eligible to be placed at any point.
3. We define a DP array dp[mask], where mask represents the set of already chosen nodes. The value stored is the maximum profit achievable after placing exactly those nodes in some valid order.
4. The transition is to try adding any node i not in mask. However, node i can only be placed if all its prerequisites are already included in mask. This is checked using bit operations.
5. If node i is valid, we compute the next mask new_mask = mask | (1 << i). The position of node i is popcount(mask) + 1, since we are building the ordering incrementally.
6. We update:

dp[new_mask] = max(dp[new_mask], dp[mask] + score[i] * position)

7. We iterate masks in increasing order so that all smaller subsets are processed before larger ones, ensuring transitions are valid.
8. The answer is dp[(1 << n) - 1], where all nodes are placed.

Why it works

The DP invariant is that dp[mask] always stores the maximum profit achievable by any valid topological ordering of exactly the nodes in mask. Since every transition respects dependency constraints, we never violate the DAG ordering rules. Because every valid topological ordering corresponds to exactly one path through this DP state space, and we explore all valid transitions, we guarantee optimality.

Python Solution

from typing import List

class Solution:
    def maxProfit(self, n: int, edges: List[List[int]], score: List[int]) -> int:
        pre = [0] * n
        for u, v in edges:
            pre[v] |= 1 << u

        dp = [-1] * (1 << n)
        dp[0] = 0

        for mask in range(1 << n):
            if dp[mask] == -1:
                continue
            cnt = bin(mask).count('1')
            for i in range(n):
                if not (mask & (1 << i)) and (mask & pre[i]) == pre[i]:
                    next_mask = mask | (1 << i)
                    dp[next_mask] = max(dp[next_mask], dp[mask] + score[i] * (cnt + 1))

        return dp[(1 << n) - 1]

The Python implementation first encodes dependencies as bitmasks. The DP array dp tracks maximum profit for each subset. We iterate through all subsets, adding eligible nodes to update profits. The bin(mask).count('1') gives the current number of nodes processed, used to compute the 1-based multiplier. prereq = [0] * n

    for u, v in edges:
        prereq[v] |= (1 << u)
    
    size = 1 << n
    dp = [-10**18] * size
    dp[0] = 0
    
    for mask in range(size):
        if dp[mask] < 0:
            continue
        
        pos = bin(mask).count("1") + 1
        
        for i in range(n):
            if mask & (1 << i):
                continue
            
            # check prerequisites
            if (prereq[i] & mask) != prereq[i]:
                continue
            
            new_mask = mask | (1 << i)
            new_score = dp[mask] + score[i] * pos
            if new_score > dp[new_mask]:
                dp[new_mask] = new_score
    
    return dp[size - 1]

### Code Explanation

We first build a prerequisite bitmask for each node, encoding all nodes that must appear before it. Then we initialize a DP array over all subsets of nodes, setting the empty set to zero profit.

For each state `mask`, we compute the current position based on how many nodes have already been selected. We then try to add each node that is not yet included. The prerequisite check ensures that we only place valid nodes according to the DAG constraints.

Each valid transition updates the DP state for the new subset. Finally, we return the full mask state representing all nodes placed.

## Go Solution

```go
func maxProfit(n int, edges [][]int, score []int) int {
    pre := make([]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        pre[v] |= 1 << u
    }

    size := 1 << n
    dp := make([]int, size)
    for i := range dp {
        dp[i] = -1
    }
    dp[0] = 0

    for mask := 0; mask < size; mask++ {
        if dp[mask] == -1 {
            continue
        }
        cnt := 0
        temp := mask
        for temp > 0 {
            cnt += temp & 1
            temp >>= 1
        }
        for i := 0; i < n; i++ {
            if mask&(1<<i) == 0 && mask&pre[i] == pre[i] {
                nextMask := mask | (1 << i)
                profit := dp[mask] + score[i]*(cnt+1)
                if profit > dp[nextMask] {
                    dp[nextMask] = profit
                }
            }
        }
    }

    return dp[size-1]
}

In Go, we handle bit counting manually instead of bin(mask).count('1'). The logic is otherwise identical to Python, iterating over masks and updating DP for valid next nodes.

Worked Examples

Example 1: n = 2, edges = [[0,1]], score = [2,3]

mask	processed nodes	eligible next node	cnt	dp update
0b00	none	0	0	dp[0b01] = 2*1 = 2
0b01	0	1	1	dp[0b11] = 2 + 3*2 = 8

Final dp[0b11] = 8

Example 2: n = 3, edges = [[0,1],[0,2]], score = [1,6,3]

mask	processed nodes	eligible next node	cnt	dp update
0b000	none	0	0	dp[0b001] = 1*1 = 1
0b001	0	1,2	1	dp[0b011] = 1 + 6_2 = 13, dp[0b101] = 1 + 3_2 = 7
0b011	0,1	2	2	dp[0b111] = 13 + 3*3 = 22
0b101	0,2	1	2	dp[0b111] = max(22, 7 + 6*3 = 25) = 25

Final dp[0b111] = 25 prereq := make([]int, n)

for _, e := range edges {
	u, v := e[0], e[1]
	prereq[v] |= 1 << u
}

size := 1 << n
dp := make([]int, size)

for i := 1; i < size; i++ {
	dp[i] = -1 << 60
}

dp[0] = 0

for mask := 0; mask < size; mask++ {
	if dp[mask] < 0 {
		continue
	}

	pos := 0
	for x := mask; x > 0; x >>= 1 {
		pos += x & 1
	}
	pos++

	for i := 0; i < n; i++ {
		if mask&(1<<i) != 0 {
			continue
		}

		if prereq[i]&mask != prereq[i] {
			continue
		}

		newMask := mask | (1 << i)
		newVal := dp[mask] + score[i]*pos

		if newVal > dp[newMask] {
			dp[newMask] = newVal
		}
	}
}

return dp[size-1]

}

### Go-specific Notes

In Go, we manually compute the population count using bit shifts instead of a built-in function. We also initialize the DP array with a very small integer value to represent negative infinity. Slice-based DP is used since Go does not have native dynamic arrays like Python lists.

## Worked Examples

### Example 1

Input:

n = 2 edges = [[0,1]] score = [2,3]

Prerequisites:

- `prereq[1] = {0}`
- `prereq[0] = {}`

DP evolution:

| mask | nodes placed | valid next nodes | dp value |
| --- | --- | --- | --- |
| 00 | {} | 0 | 0 |
| 01 | {0} | 1 | 2 |
| 11 | {0,1} | none | 8 |

Step details:

1. Start with `mask = 00`, position = 1
2. Place node 0 → profit = 2 * 1 = 2
3. From mask `01`, position = 2
4. Place node 1 → profit = 3 * 2 = 6
5. Total = 8

Final answer = 8

### Example 2

Input:

n = 3 edges = [[0,1],[0,2]] score = [1,6,3]

Prerequisites:

- `prereq[1] = {0}`
- `prereq[2] = {0}`

DP highlights:

| mask | valid nodes | best action |
| --- | --- | --- |
| 000 | 0 | start |
| 001 | 1,2 invalid (need 0) | place 0 |
| 001 (after 0) | 1,2 | choose 2 first |
| 011 | 1 | then 1 |

Optimal sequence: `[0,2,1]`

Profit:

- 0 at pos 1 → 1
- 2 at pos 2 → 6
- 1 at pos 3 → 18

Total = 25

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n * 2^n) | Iterates over 2^n subsets and for each subset checks n nodes for eligibility |
| Space | O(2^n) | Stores DP for each subset mask |

The DP approach is feasible because `n <= 22`, making `2^n ≈ 4 million`, which is acceptable for modern computation.
| Time | O(n · 2^n) | Each subset is processed, and for each subset we try up to n nodes |
| Space | O(2^n + n) | DP array of size 2^n and prerequisite masks |

The exponential complexity is acceptable because `n ≤ 22`, making `2^n ≈ 4 million`, which is feasible with efficient transitions.

## Test Cases

sol = Solution()

Example 1

assert sol.maxProfit(2, [[0,1]], [2,3]) == 8 # simple two-node DAG

Example 2

assert sol.maxProfit(3, [[0,1],[0,2]], [1,6,3]) == 25 # forked DAG

Single node

assert sol.maxProfit(1, [], [10]) == 10

Linear DAG

assert sol.maxProfit(4, [[0,1],[1,2],[2,3]], [1,2,3,4]) == 30 # 11 + 22 + 33 + 44 = 30

Independent nodes

assert sol.maxProfit(3, [], [5,10,1]) == 31 # order nodes descending by score: 11+102+5*3 = 31

Complex DAG

assert sol.maxProfit(4, [[0,1],[0,2],[1,3],[2,3]], [3,2,1,4]) == 29

| Test | Why |
assert Solution().maxProfit(2, [[0,1]], [2,3]) == 8  # basic chain dependency

assert Solution().maxProfit(3, [[0,1],[0,2]], [1,6,3]) == 25  # branching dependency optimal ordering

assert Solution().maxProfit(3, [], [1,2,3]) == 14  # no edges, best descending order

assert Solution().maxProfit(1, [], [10]) == 10  # single node

assert Solution().maxProfit(4, [[0,1],[1,2],[2,3]], [1,1,1,1]) == 10  # strict chain

assert Solution().maxProfit(3, [[1,2]], [5,1,10]) == 35  # independent + dependency mix

Test	Why
single edge chain	validates basic dependency handling
branching DAG	tests optimal ordering choice
no edges	checks permutation optimization
single node	minimal boundary case
long chain	ensures strict ordering propagation
mixed constraints	validates partial dependency structure

Edge Cases

One important edge case is when the graph has no edges. In this case, every permutation is valid, and the algorithm should automatically choose descending score values first since earlier positions have smaller multipliers. The DP naturally handles this because it will always pick high-value nodes earlier to maximize contribution.

Another edge case is a fully linear chain of dependencies. Here, there is exactly one valid topological order. The DP should behave like a simple accumulation, and any deviation would indicate incorrect prerequisite handling.

A third edge case involves multiple independent subgraphs. In such cases, the optimal solution interleaves nodes from different components based on score magnitude. The DP correctly handles this because independence means prerequisite masks are empty across components, allowing flexible ordering decisions.