# Maximum Profit from Valid Topological Order in DAG
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-profit-from-valid-topological-order-in-dag)
Canonical: https://scaleengineer.com/dsa/problems/maximum-profit-from-valid-topological-order-in-dag
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Array, Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-profit-from-valid-topological-order-in-dag/image0.png)

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:**

![](https://assets.glich.co/dsa/maximum-profit-from-valid-topological-order-in-dag/image1.png)

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.

# Approaches
## Brute-Force by Checking All Permutations
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.
**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.
**Pros:** Conceptually simple and straightforward to understand.
**Cons:** Extremely inefficient due to the factorial time complexity.; Not feasible for the given constraints (`n` up to 22).
### Explanation
The algorithm proceeds as follows:
1.  Generate all `n!` permutations of the nodes `0, 1, ..., n-1`.
2.  For each permutation `P`:
    a.  Check if `P` is a valid topological sort. To do this, we can create a mapping from each node to its position in `P`. Then, for every edge `u -> v` in the graph, we check if `position[u] < position[v]`. If this condition holds for all edges, the permutation represents a valid topological order.
    b.  If `P` is valid, calculate its profit. The profit is the sum of `score[P[i]] * (i + 1)` for `i` from 0 to `n-1`.
    c.  Keep track of the maximum profit found so far.
3.  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.

```java
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);
    }
}
```
### Algorithm
- Generate all `n!` permutations of the nodes `0, 1, ..., n-1`.
- For each permutation `P`:
  - Check if `P` is a valid topological sort by verifying that for every edge `u -> v`, `u` appears before `v` in `P`.
  - If `P` is valid, calculate its profit: `Σ(score[P[i]] * (i+1))`.
  - Update the overall maximum profit.
- Return the maximum profit.

## Dynamic Programming with Bitmasking
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.
**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`.
**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.
### Explanation
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.

```java
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];
    }
}
```
### Algorithm
- Pre-calculate a predecessor mask for each node. `pred_mask[i]` is a bitmask where the `j`-th bit is 1 if `j -> i` is an edge.
- Initialize a DP array `dp` of size `2^n`. `dp[mask]` will store the max profit for the nodes in `mask`. Set `dp[0] = 0` and 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`, let `k = popcount(mask)`.
- Iterate through each node `u` from 0 to `n-1`.
- If `u` is in `mask`:
  - Let `prev_mask = mask \ {u}`.
  - Check if all predecessors of `u` are in `prev_mask` using `(pred_mask[u] & prev_mask) == pred_mask[u]`.
  - If the condition holds and `dp[prev_mask]` is a valid state, update `dp[mask]` with `max(dp[mask], dp[prev_mask] + score[u] * k)`.
- The final answer is `dp[(1 << n) - 1]`.

## Greedy Approach with Priority Queue (Kahn's Algorithm)
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.
**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.
**Pros:** Highly efficient and optimal for this problem.; Relatively simple to implement using standard graph algorithms.; Scales well for much larger `n` and `E` than the other approaches.
**Cons:** The proof of optimality, while correct, is based on an exchange argument which might not be immediately obvious.
### Explanation
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.

```java
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;
    }
}
```
### 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 = 0` and `position = 1`.
- While the priority queue is not empty:
  - Extract the node `u` with the minimum score.
  - Add its profit contribution: `totalProfit += score[u] * position`.
  - Increment `position`.
  - For each neighbor `v` of `u`:
    - Decrement the in-degree of `v`.
    - If `v`'s in-degree becomes 0, add it to the priority queue.
- Return `totalProfit`.