How should I practice Maximum K-Star Sum?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Akuna Capital online assessment problems in FastPrep.

Is Maximum K-Star Sum associated with Akuna Capital?

FastPrep tags this as a Akuna Capital coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Graph

Maximum K-Star Sum

Learn this problem

● MediumAkuna CapitalOA

Problem statement

You are given an undirected graph with g_nodes nodes and g_edges edges, together with an integer k. The nodes are numbered from 1 to g_nodes. Edge i connects g_from[i] and g_to[i].

A k-star is a non-empty subgraph that forms a star: one selected node is the center, and every other selected node is directly connected to that center. The star may have at most k arms.

Node i has value values[i - 1]. The sum of a k-star is the sum of the values of all nodes in the subgraph.

The illustration accompanying the example shows valid stars with 3 through 6 arms. The orange node is the center, every blue node is an arm, and every line is an edge.

A k-star does not need to have exactly k arms; k is only the upper limit. Find the maximum possible sum of a k-star.

Function

getMaximumSumKStar(g_nodes: int, g_from: int[], g_to: int[], values: int[], k: int) → int

Examples

Example 1

g_nodes = 5g_from = [3,3,3,3]g_to = [1,2,4,5]values = [10,20,30,40,50]k = 2return = 120

The graph is a star centered on node 3. With k = 2, choose node 3 as the center and nodes 4 and 5 as its arms. Their values sum to 30 + 40 + 50 = 120, which is the maximum.

Constraints

1 <= values.length = g_nodes.
g_from.length = g_to.length = g_edges.
Every edge joins two valid, distinct node numbers from 1 through g_nodes.
The graph is undirected and has no duplicate edges.
0 <= k.