largest sum problem

 avatar
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_) ;
        }
    }
}
Leave a Comment