# largest sum problem

bruteCoder
java
2 months ago
1.7 kB
3
Indexable
Never
```import java.util.Map ;
import java.util.HashMap ;
import java.util.Scanner;

public class LongestSumCycle_juspay {
public static void main(String[] args) {
SOLVEJUSAPAYOA object = new SOLVEJUSAPAYOA() ;
Scanner sc = new Scanner(System.in) ;
int N = sc.nextInt() ;
int[] edges = new int[N] ;
for (int i = 0 ; i < N ; i++)
edges[i] = sc.nextInt() ;

System.out.println(object.GetLongestSumCycle(N , edges));
}
}
class SOLVEJUSAPAYOA{
private int MaxSum ;

public int GetLongestSumCycle(int N , int[] edges) {
MaxSum = Integer.MIN_VALUE ;
boolean[] visited = new boolean[N] ;
Map<Integer,Integer> sum   = new HashMap<>() ;
Map<Integer,Integer> count = new HashMap<>() ;
int cycle = 1 ;
for (int i = 0 ; i < N ; i ++) {
if(!visited[i]){
int _SUM_ = 0 ;
dfs(i,visited, edges , sum,count,_SUM_,cycle) ;
cycle++ ;
}
}
return MaxSum ;
}

private void dfs(int src, boolean[] visited, int[] edges, Map<Integer, Integer> sum, Map<Integer, Integer> count  , int SUM , int cycle) {
visited[src] = true ;
SUM += src ;
sum.put(src , SUM) ;
count.put(src , cycle) ;
int neighbor = edges[src] ;
if(neighbor == -1)
return ;
if(!visited[neighbor])
dfs(neighbor , visited , edges , sum , count , SUM, cycle);
else if(sum.containsKey(neighbor) && (count.get(src) == count.get(neighbor))){
int _SUM_ = sum.get(src) - sum.get(neighbor) + neighbor ;
MaxSum = Math.max(MaxSum , _SUM_) ;
}
}
}```