3530. Maximum Profit from Valid Topological Order in DAG LeetCode Solution

Last updated: May 5, 2025

In this guide, you will get 3530. Maximum Profit from Valid Topological Order in DAG LeetCode Solution with the best time and space complexity. The solution to Maximum Profit from Valid Topological Order in DAG problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Maximum Profit from Valid Topological Order in DAG solution in C++
  4. Maximum Profit from Valid Topological Order in DAG solution in Java
  5. Maximum Profit from Valid Topological Order in DAG solution in Python
  6. Additional Resources
3530. Maximum Profit from Valid Topological Order in DAG LeetCode Solution image

Problem Statement of Maximum Profit from Valid Topological Order in DAG

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.

Complexity Analysis

  • Time Complexity: O(n \cdot 2^n)
  • Space Complexity: O(2^n)

3530. Maximum Profit from Valid Topological Order in DAG LeetCode Solution in C++

class Solution {
 public:
  int maxProfit(int n, vector<vector<int>>& edges, vector<int>& score) {
    const int maxMask = 1 << n;
    // need[i] := the bitmask representing all nodes that must be placed before
    // node i
    vector<int> need(n);
    // dp[mask] := the maximum profit achievable by placing the set of nodes
    // represented by `mask`
    vector<int> dp(maxMask, -1);
    dp[0] = 0;

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      need[v] |= 1 << u;
    }

    // Iterate over all subsets of nodes (represented by bitmask `mask`)
    for (unsigned mask = 0; mask < maxMask; ++mask) {
      if (dp[mask] == -1)
        continue;
      // Determine the position of the next node to be placed (1-based).
      const int pos = popcount(mask) + 1;
      // Try to place each node `i` that hasn't been placed yet.
      for (int i = 0; i < n; ++i) {
        if (mask >> i & 1)
          continue;
        // Check if all dependencies of node `i` are already placed.
        if ((mask & need[i]) == need[i]) {
          const int newMask = mask | 1 << i;  // Mark node `i` as placed.
          dp[newMask] = max(dp[newMask], dp[mask] + score[i] * pos);
        }
      }
    }

    return dp.back();
  }
};
/* code provided by PROGIEZ */

3530. Maximum Profit from Valid Topological Order in DAG LeetCode Solution in Java

class Solution {
  public int maxProfit(int n, int[][] edges, int[] score) {
    final int maxMask = 1 << n;
    // need[i] := the bitmask representing all nodes that must be placed before node i
    int[] need = new int[n];
    // dp[mask] := the maximum profit achievable by placing the set of nodes represented by `mask`
    int[] dp = new int[maxMask];
    Arrays.fill(dp, -1);
    dp[0] = 0;

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      need[v] |= 1 << u;
    }

    // Iterate over all subsets of nodes (represented by bitmask `mask`)
    for (int mask = 0; mask < maxMask; ++mask) {
      if (dp[mask] == -1)
        continue;
      // Determine the position of the next node to be placed (1-based).
      int pos = Integer.bitCount(mask) + 1;
      // Try to place each node `i` that hasn't been placed yet.
      for (int i = 0; i < n; ++i) {
        if ((mask >> i & 1) == 1)
          continue;
        // Check if all dependencies of node `i` are already placed.
        if ((mask & need[i]) == need[i]) {
          final int newMask = mask | 1 << i; // Mark node `i` as placed.
          dp[newMask] = Math.max(dp[newMask], dp[mask] + score[i] * pos);
        }
      }
    }

    return dp[maxMask - 1];
  }
}
// code provided by PROGIEZ

3530. Maximum Profit from Valid Topological Order in DAG LeetCode Solution in Python

class Solution:
  def maxProfit(self, n: int, edges: list[list[int]], score: list[int]) -> int:
    # need[i] := the bitmask representing all nodes that must be placed before
    # node i
    need = [0] * n
    # dp[mask] := the maximum profit achievable by placing the set of nodes
    # represented by `mask`
    dp = [-1] * (1 << n)
    dp[0] = 0

    for u, v in edges:
      need[v] |= 1 << u

    # Iterate over all subsets of nodes (represented by bitmask `mask`)
    for mask in range(1 << n):
      if dp[mask] == -1:
        continue
      # Determine the position of the next node to be placed (1-based).
      pos = mask.bit_count() + 1
      # Try to place each node `i` that hasn't been placed yet.
      for i in range(n):
        if mask >> i & 1:
          continue
        # Check if all dependencies of node `i` are already placed.
        if (mask & need[i]) == need[i]:
          newMask = mask | 1 << i  # Mark node `i` as placed.
          dp[newMask] = max(dp[newMask], dp[mask] + score[i] * pos)

    return dp[-1]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.