Maximum K-Star Sum
C3.ai● MediumNEW GRADOAProblem statement
Given an undirected graph with g_nodes vertices numbered from 0 to g_nodes - 1, an integer value for each vertex, and a nonnegative integer k, find the maximum sum of a nonempty k-star.
A star consists of one center vertex and at most k distinct vertices adjacent to that center. Each selected neighbor contributes one arm. A center with no arms is allowed. The star's sum includes the center's value and the values of all selected neighbors.
The edges are described by equally sized arrays g_from and g_to: edge i joins g_from[i] and g_to[i]. Vertex i has value values[i].
Return the largest possible sum over all choices of center and arms. The graph has no self-loops or repeated edges. Edges between selected neighbors do not prevent choosing them: the star is a subgraph, not necessarily an induced subgraph.
Function
bestSumKStar(g_nodes: int, g_from: int[], g_to: int[], values: int[], k: int) → intExamples
Example 1
g_nodes = 7g_from = [0,0,0,3,3,3]g_to = [1,2,3,4,5,6]values = [1,-2,3,4,5,-1,-2]k = 2return = 10Use vertex 3 as the center and vertices 4 and 0 as arms. The sum is 4 + 5 + 1 = 10. Negative neighbors need not be selected.
Example 2
g_nodes = 2g_from = [0]g_to = [1]values = [-5,-2]k = 0return = -2No arms are allowed. The better nonempty star consists only of vertex 1, with value -2. An empty star with sum 0 is not allowed.
Example 3
g_nodes = 3g_from = [0,1,0]g_to = [1,2,2]values = [-10,4,9]k = 3return = 13Choose vertex 2 and its positive neighbor 1. Their sum is 13. Using fewer than k arms is allowed.
Constraints
2 <= g_nodes <= 10^5.1 <= g_from.length = g_to.length <= 10^5.0 <= g_from[i], g_to[i] < g_nodes.values.length = g_nodesand-10^3 <= values[i] <= 10^3.0 <= k <= 10^5.- The graph is undirected and has no self-loops or repeated edges.