Largest Sum Cycle
Problem Overview
Each cell has at most one outgoing edge, and a value of minus 1 means the cell stops.
Intuition
Each cell has at most one outgoing edge, and a value of minus 1 means the cell stops. Following edges from any cell walks a single chain. The chain reaches a cell with no outgoing edge, joins a chain that was already finished, or returns to a cell that is still on the current chain. That last case closes a cycle. A chain holds at most one cycle, and the cells that only lead into the cycle stay outside the sum. A cell is marked active while its chain is being followed. When the next cell is still active, the walk has looped. Starting at that cell and following edges until it reappears adds each cycle index once. The sum is a 64 bit integer, because a cycle through a long array can pass 2 to the 31. The same chain is then walked again and every active cell is marked finished. A later start that runs into a finished cell stops there. Those outgoing edges were already explored, so that chain holds no new cycle. When no chain ever closes, the answer stays minus 1.
Algorithm
- 1Mark every cell unvisited, and start the best sum at minus 1.
- 2From each unvisited cell, follow edges and mark cells active until the next cell is missing, already active, or finished.
- 3When the next cell is active, add the indices around that cycle and keep the larger sum.
- 4Walk the chain again and mark every active cell finished.
- 5Return the best sum. The result stays minus 1 when no cycle was closed.
Example Walkthrough
Input: edge = [1, 2, 0, -1]
- 1. From cell 0 the chain visits 0, then 1, then 2, and the next step returns to 0.
- 2. The cycle indices are 0, 1, and 2. Their sum is 3.
- 3. Cell 3 has no outgoing edge, so that chain adds no cycle.
Output: 3
Common Pitfalls
- • Cells that only lead into a cycle stay outside the sum. The sum starts at the cell where the chain meets itself.
- • Mark the chain finished after it is scored. A later start that reaches a finished cell ends there.
- • The cycle sum is a 64 bit integer. Adding every index of a long cycle overflows a 32 bit total.
- • A cell whose edge is minus 1 ends the chain. A cycle needs the walk to return to an active cell.
// Approach: Each cell has one outgoing edge, so every chain leads into a
// cycle or a dead end. A cell is marked while its chain is being followed,
// then marked finished. Meeting a cell that is still on the current chain
// closes a cycle. The indices on that cycle are added once, and the largest
// sum is kept. A chain that reaches a finished cell or a cell with no edge
// adds no cycle. The sum is a 64 bit integer.
// Complexity: O(n) time, O(n) extra space.
class Solution {
public int largestSumCycle(int[] edge) {
int n = edge.length;
int[] state = new int[n];
long best = -1;
for (int start = 0; start < n; start++) {
if (state[start] != 0)
continue;
int node = start;
while (node != -1 && state[node] == 0) {
state[node] = 1;
node = edge[node];
}
if (node != -1 && state[node] == 1) {
long sum = 0;
int cur = node;
do {
sum += cur;
cur = edge[cur];
} while (cur != node);
if (sum > best)
best = sum;
}
node = start;
while (node != -1 && state[node] == 1) {
state[node] = 2;
node = edge[node];
}
}
return (int) best;
}
}