Problem · Graph
Converging Maze: Largest Sum Cycle
Learn this problemProblem statement
You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (i.e. entry/exit points are unidirectional doors like valves).
The cells are named with an integer value from 0 to N-1.
You have to find:
The sum of the largest sum cycle in the maze. Return -1 if there are no cycles.
Sum of a cycle is the sum of the node number of all nodes in that cycle.
Function
largestSumCycle(edge: int[]) → long
Complete largestSumCycle with the following parameter:
int[] edge: an array of lengthN, whereedge[i]is the cell reached from celliin one step, or-1when cellihas no exit. The value ofNisedge.length.
Returns
long: the largest sum of cell numbers in any cycle, or -1 if the maze has no cycle
🤗 A very special thanks to a fantastic friend for all the help!
Examples
Example 1
edge = [4, 4, 1, 4, 13, 8, 8, 8, 0, 8, 14, 9, 15, 11, -1, 10, 15, 22, 22, 22, 22, 22, 21]return = 45The cycle 9 → 8 → 0 → 4 → 13 → 11 → 9 has node sum 9 + 8 + 0 + 4 + 13 + 11 = 45, the largest cycle sum.
Constraints
1 ≤ edge.length ≤ 105-1 ≤ edge[i] < edge.length