#2497

Maximum Star Sum of a Graph

specialist · 995 · lc medium +32 · verified · 42% accepted · 451 likes · top 23%

Description

Given an undirected graph with n nodes (0-indexed), node values array vals, and edge list edges, a star graph consists of a center node and zero or more of its neighbors connected by edges sharing that center. The star sum is the total value of all nodes in the star. Return the maximum star sum achievable using at most k edges.

Example 1:

Input: vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2

Output: 16

Explanation: The above diagram represents the input graph.

The star graph with the maximum star sum is denoted by blue. It is centered at 3 and includes its neighbors 1 and 4.

It can be shown it is not possible to get a star graph with a sum greater than 16.

Example 2:

Input: vals = [-5], edges = [], k = 0

Output: -5

Explanation: There is only one possible star graph, which is node 0 itself.

Hence, we return -5.

Code

1

2

3

class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:

class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int: