Maximum Star Sum of a Graph

Solution

• Build an Adjacency List: Traverse the edges, but instead of just storing the neighbor's ID, store the neighbor's value. To save time, you can even filter out negative values immediately.
• Sort the Neighbors: Go through every node's list of positive neighbors and sort them in descending order (highest value first).
• Calculate and Maximize: For each node, start your sum with the node's own value. Then, grab the top $k$ values from its sorted neighbor list and add them to the sum. Keep a global tracker for the highest sum you've seen across all nodes.

Implementation

• Optimal approach:

import math
from collections import defaultdict

class Solution:
    def maxStarSum(self, vals: list[int], edges: list[list[int]], k: int) -> int:
        # Step 1: Build the graph, tracking ONLY positive neighbor values
        graph = defaultdict(list)
        for u, v in edges:
            if vals[v] > 0:
                graph[u].append(vals[v])
            if vals[u] > 0:
                graph[v].append(vals[u])
        
        max_star_sum = -math.inf
        
        # Step 2 & 3: Check every node as a potential center
        for i, center_val in enumerate(vals):
            # Sort this center's positive neighbors from largest to smallest
            neighbors = sorted(graph[i], reverse=True)
            
            # Take at most k neighbors
            current_star_sum = center_val + sum(neighbors[:k])
            
            # Update the global maximum
            max_star_sum = max(max_star_sum, current_star_sum)
            
        return max_star_sum