Maximum Star Sum of a Graph
Problem statement
You are given an undirected graph with $n$ nodes labeled $0 \dots n-1$. Node $i$ has value $\mathrm{vals}[i]$ (values may be negative). You are also given a list $\mathrm{edges}$, where $\mathrm{edges}[j] = [u, v]$ is an undirected edge, and an integer $k$.
A star graph is a subgraph made of one node (the center) together with at most $k$ of its direct neighbors. The star sum is the sum of the values of all nodes in the star (the center plus the chosen neighbors).
Return the maximum star sum over every choice of center and neighbors.
Constraints:
- $1 \le n \le 10^5$
- $\mathrm{vals}[i]$ may be negative or positive
- $0 \le k \le n - 1$
Examples:
- $\mathrm{vals} = [1,2,3,4,10,-10,-20]$, $\mathrm{edges} = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]]$, $k = 2 \to 16$. Center node $3$ (value $4$) plus its two best neighbors, node $4$ ($10$) and node $1$ ($2$): $4 + 10 + 2 = 16$.
- $\mathrm{vals} = [-5]$, $\mathrm{edges} = []$, $k = 0 \to -5$. The only star is the lone node.
Show hint
If you fix the centre first, do the choices of which neighbours to include affect each other at all?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.