Maximum profit from valid topological order in dag

Array Dynamic Programming Bit Manipulation Graph Theory Topological Sort Bitmask

29.8% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_profit(n: i32, edges: Vec<Vec<i32>>, score: Vec<i32>) -> i32 {
    let n = n as usize;
    // prereq[v] = bitmask of nodes that must come before v
    let mut prereq = vec![0u32; n];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      prereq[v] |= 1 << u;
    }

    // dp[mask] = max profit when exactly the nodes in mask have been processed
    let mut dp = vec![i64::MIN; 1 << n];
    dp[0] = 0;

    for mask in 0u32..(1u32 << n) {
      if dp[mask as usize] == i64::MIN { continue; }
      let pos = mask.count_ones() as i64 + 1; // next 1-based position
      for v in 0..n {
        if mask & (1 << v) != 0 { continue; } // already processed
        if (prereq[v] & mask) != prereq[v] { continue; } // prereqs not met
        let next = mask | (1 << v);
        let profit = dp[mask as usize] + score[v] as i64 * pos;
        if profit > dp[next as usize] {
          dp[next as usize] = profit;
        }
      }
    }

    let full = (1u32 << n) - 1;
    dp[full as usize] as i32
  }
}