Maximum difference between node and its ancestor in a Directed Acyclic Graph ( DAG ) | Java program for the above approach ; Function to perform DFS Traversal on the given graph ; Update the value of ans ; Update the currentMin and currentMax ; Traverse the adjacency list of the node src ; Recursively call for the child node ; Function to calculate maximum absolute difference between a node and its ancestor ; Stores the adjacency list of graph ; Create Adjacency list ; Add a directed edge ; Perform DFS Traversal ; Print the maximum absolute difference ; Driver code
import java . util . * ; class GFG { static int ans ; static void DFS ( int src , ArrayList < ArrayList < Integer > > Adj , int arr [ ] , int currentMin , int currentMax ) { ans = Math . max ( ans , Math . max ( Math . abs ( currentMax - arr [ src - 1 ] ) , Math . abs ( currentMin - arr [ src - 1 ] ) ) ) ; currentMin = Math . min ( currentMin , arr [ src - 1 ] ) ; currentMax = Math . min ( currentMax , arr [ src - 1 ] ) ; for ( Integer child : Adj . get ( src ) ) { DFS ( child , Adj , arr , currentMin , currentMax ) ; } } static void getMaximumDifference ( int Edges [ ] [ ] , int arr [ ] , int N , int M ) { ans = 0 ; ArrayList < ArrayList < Integer > > Adj = new ArrayList < > ( ) ; for ( int i = 0 ; i < N + 1 ; i ++ ) Adj . add ( new ArrayList < > ( ) ) ; for ( int i = 0 ; i < M ; i ++ ) { int u = Edges [ i ] [ 0 ] ; int v = Edges [ i ] [ 1 ] ; Adj . get ( u ) . add ( v ) ; } DFS ( 1 , Adj , arr , arr [ 0 ] , arr [ 0 ] ) ; System . out . println ( ans ) ; } public static void main ( String [ ] args ) { int N = 5 , M = 4 ; int Edges [ ] [ ] = { { 1 , 2 } , { 2 , 3 } , { 4 , 5 } , { 1 , 3 } } ; int arr [ ] = { 13 , 8 , 3 , 15 , 18 } ; getMaximumDifference ( Edges , arr , N , M ) ; } }