import java.util.* ;
import java.lang.* ;
class Main
{
public static void main
( String args
[ ] ) {
int [ ] [ ] array = { { 4 ,- 2 ,3 ,6 }
,{ 9 ,10 ,- 4 ,1 }
,{ - 1 ,2 ,1 ,4 }
,{ 0 ,3 ,7 ,- 3 } } ;
int max = recursionAlg( array,array.length - 1 ,0 ,route) ;
int max2 = loopAlg( array,array.length - 1 ,0 ,route2) ;
System .
out .
println ( "The max food in the recursion solution is: " + max
) ; System .
out .
println ( "and the route is: " ) ; printRouteArray( route) ;
System .
out .
println ( "The max food in the loop solution: " + max2
) ; System .
out .
println ( "The route is: " ) ; printRouteArray( route2) ;
}
public enum Dirs { START, FROM_LEFT, FROM_DOWN} ;
public static int loopAlg
( int [ ] [ ] arr,
int x,
int y,
String [ ] route
) {
int n= 0 ;
int [ ] [ ] count = new int [ arr.length ] [ arr[ 0 ] .length ] ;
Dirs[ ] [ ] directions = new Dirs[ arr.length ] [ arr[ 0 ] .length ] ;
List< String> path = new ArrayList< String> ( ) ;
for ( int i = x; i>= 0 ; i-- )
{
for ( int j = 0 ; j< arr[ 0 ] .length ; j++ )
{
if ( i== x && j== 0 ) { count[ i] [ j] = arr[ i] [ j] ; directions[ i] [ j] = Dirs.START ; }
else if ( i == x) { count[ i] [ j] = count[ i] [ j- 1 ] + arr[ i] [ j] ; directions[ i] [ j] = Dirs.FROM_LEFT ; }
else if ( j == 0 ) { count[ i] [ j] = count[ i+ 1 ] [ j] + arr[ i] [ j] ; directions[ i] [ j] = Dirs.FROM_DOWN ; }
else {
if ( count[ i] [ j- 1 ] > count[ i+ 1 ] [ j] ) { count[ i] [ j] = count[ i] [ j- 1 ] + arr[ i] [ j] ; directions[ i] [ j] = Dirs.FROM_LEFT ; }
else { count[ i] [ j] = count[ i+ 1 ] [ j] + arr[ i] [ j] ; directions[ i] [ j] = Dirs.FROM_DOWN ; }
}
}
}
int i= 0 , j= arr[ 0 ] .length - 1 ;
while ( directions[ i] [ j] != Dirs.START ) {
if ( directions[ i] [ j] == Dirs.FROM_LEFT ) {
path.add ( "Right" ) ;
j--;
}
else {
path.add ( "Up" ) ;
i++;
}
}
i= 0 ;
route[ i] = part;
i++;
}
return count[ 0 ] [ arr[ 0 ] .length - 1 ] ;
}
public static int recursionAlg
( int [ ] [ ] arr,
int x,
int y,
String [ ] route
) {
return recursionAlg( arr,0 ,x,y,arr[ 0 ] .length - 1 ,route,0 ) ;
}
public static int recursionAlg
( int [ ] [ ] arr,
int count,
int x,
int y,
int max_y,
String [ ] route,
int i
) {
if ( x == 0 && y == max_y) { return count; }
else if ( x == 0 ) {
route[ i] = "Right" ;
return recursionAlg( arr,count+ arr[ x] [ y+ 1 ] ,x,y+ 1 ,max_y,route,i+ 1 ) ;
}
else if ( y== max_y) {
route[ i] = "Up" ;
return recursionAlg( arr,count+ arr[ x- 1 ] [ y] ,x- 1 ,y,max_y,route,i+ 1 ) ;
}
else if ( recursionAlg( arr,count+ arr[ x- 1 ] [ y] ,x- 1 ,y,max_y,route,i+ 1 ) > recursionAlg( arr,count+ arr[ x] [ y+ 1 ] ,x,y+ 1 ,max_y,route,i+ 1 ) )
{
route[ i] = "Up" ;
return recursionAlg( arr,count+ arr[ x- 1 ] [ y] ,x- 1 ,y,max_y,route,i+ 1 ) ;
}
else
{
route[ i] = "Right" ;
return recursionAlg( arr,count+ arr[ x] [ y+ 1 ] ,x,y+ 1 ,max_y,route,i+ 1 ) ;
}
}
public static void printRouteArray
( String [ ] arr
) {
int i= 0 ;
while ( i< arr.length && arr[ i] != null )
{
System .
out .
print ( arr
[ i
] + "-->" ) ; i++;
}
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CgpjbGFzcyBNYWluCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZyBhcmdzW10pCnsKICAgIFN0cmluZ1tdIHJvdXRlID0gbmV3IFN0cmluZ1sxMDBdOyAgICAgICAgICAgICAgICAgIAogICAgaW50W11bXWFycmF5ID0ge3s0LC0yLDMsNn0KICAgICAgICAgICAgICAgICAgICAsezksMTAsLTQsMX0KICAgICAgICAgICAgICAgICAgICAsey0xLDIsMSw0fQogICAgICAgICAgICAgICAgICAgICx7MCwzLDcsLTN9fTsKICAgIFN0cmluZ1tdIHJvdXRlMiA9IG5ldyBTdHJpbmdbMTAwXTsgICAgICAgICAgICAgICAgCiAgICBpbnQgbWF4ID0gcmVjdXJzaW9uQWxnKGFycmF5LGFycmF5Lmxlbmd0aC0xLDAscm91dGUpOyAgICAgICAgCiAgICBpbnQgbWF4MiA9IGxvb3BBbGcoYXJyYXksYXJyYXkubGVuZ3RoLTEsMCxyb3V0ZTIpOwogICAgU3lzdGVtLm91dC5wcmludGxuKCJUaGUgbWF4IGZvb2QgaW4gdGhlIHJlY3Vyc2lvbiBzb2x1dGlvbiBpczogIittYXgpOwogICAgU3lzdGVtLm91dC5wcmludGxuKCJhbmQgdGhlIHJvdXRlIGlzOiAiKTsKICAgIHByaW50Um91dGVBcnJheShyb3V0ZSk7CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oIlRoZSBtYXggZm9vZCBpbiB0aGUgbG9vcCBzb2x1dGlvbjogIittYXgyKTsKICAgIFN5c3RlbS5vdXQucHJpbnRsbigiVGhlIHJvdXRlIGlzOiAiKTsKICAgIHByaW50Um91dGVBcnJheShyb3V0ZTIpOwp9CgpwdWJsaWMgZW51bSBEaXJzIHtTVEFSVCwgRlJPTV9MRUZULCBGUk9NX0RPV059OwoKcHVibGljIHN0YXRpYyBpbnQgbG9vcEFsZyhpbnQgW11bXSBhcnIsaW50IHgsIGludCB5LCBTdHJpbmdbXSByb3V0ZSkKewogICAgCiAgICBpbnQgbj0wOwogICAgaW50W11bXWNvdW50ID0gbmV3IGludFthcnIubGVuZ3RoXVthcnJbMF0ubGVuZ3RoXTsKICAgIERpcnNbXVtdIGRpcmVjdGlvbnMgPSBuZXcgRGlyc1thcnIubGVuZ3RoXVthcnJbMF0ubGVuZ3RoXTsKICAgIExpc3Q8U3RyaW5nPiBwYXRoID0gbmV3IEFycmF5TGlzdDxTdHJpbmc+KCk7CiAgICAKICAgIGZvcihpbnQgaSA9IHg7IGk+PTAgOyBpLS0pCiAgICB7CiAgICAgICAgZm9yKGludCBqID0gMDsgajxhcnJbMF0ubGVuZ3RoOyBqKyspCiAgICAgICAgewogICAgICAgICAgICBpZiAoaT09eCAmJiBqPT0wKSB7Y291bnRbaV1bal09YXJyW2ldW2pdOyBkaXJlY3Rpb25zW2ldW2pdID0gRGlycy5TVEFSVDt9CiAgICAgICAgICAgIGVsc2UgaWYgKGkgPT0geCkgeyBjb3VudFtpXVtqXT1jb3VudFtpXVtqLTFdK2FycltpXVtqXTsgZGlyZWN0aW9uc1tpXVtqXSA9IERpcnMuRlJPTV9MRUZUO30KICAgICAgICAgICAgZWxzZSBpZiAoaiA9PSAwKSB7IGNvdW50W2ldW2pdPWNvdW50W2krMV1bal0rYXJyW2ldW2pdOyBkaXJlY3Rpb25zW2ldW2pdID0gRGlycy5GUk9NX0RPV047fQogICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgaWYgKGNvdW50W2ldW2otMV0+Y291bnRbaSsxXVtqXSkge2NvdW50W2ldW2pdPWNvdW50W2ldW2otMV0rYXJyW2ldW2pdO2RpcmVjdGlvbnNbaV1bal0gPSBEaXJzLkZST01fTEVGVDt9CiAgICAgICAgICAgICAgICBlbHNlIHsgY291bnRbaV1bal09IGNvdW50W2krMV1bal0rYXJyW2ldW2pdO2RpcmVjdGlvbnNbaV1bal0gPSBEaXJzLkZST01fRE9XTjt9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBpbnQgaT0wLCBqPWFyclswXS5sZW5ndGgtMTsKICAgIHdoaWxlKGRpcmVjdGlvbnNbaV1bal0hPSBEaXJzLlNUQVJUKSB7CiAgICAgICAgaWYoZGlyZWN0aW9uc1tpXVtqXSA9PSBEaXJzLkZST01fTEVGVCkgewogICAgICAgICAgICBwYXRoLmFkZCgiUmlnaHQiKTsKICAgICAgICAgICAgai0tOwogICAgICAgIH0KICAgICAgICBlbHNlIHsKICAgICAgICAgICAgcGF0aC5hZGQoIlVwIik7CiAgICAgICAgICAgIGkrKzsKICAgICAgICB9CiAgICB9CiAgICBDb2xsZWN0aW9ucy5yZXZlcnNlKHBhdGgpOwogICAgaT0wOwogICAgZm9yKFN0cmluZyBwYXJ0OnBhdGgpIHsKICAgICAgICByb3V0ZVtpXSA9IHBhcnQ7CiAgICAgICAgaSsrOwogICAgfQogICAgICAgIAogICAgcmV0dXJuIGNvdW50WzBdW2FyclswXS5sZW5ndGgtMV07Cn0gICAKCnB1YmxpYyBzdGF0aWMgaW50IHJlY3Vyc2lvbkFsZyhpbnQgW11bXSBhcnIsIGludCB4LCBpbnQgeSxTdHJpbmdbXSByb3V0ZSkKewogICAgcmV0dXJuIHJlY3Vyc2lvbkFsZyhhcnIsMCx4LHksYXJyWzBdLmxlbmd0aC0xLHJvdXRlLDApOyAgICAgICAgCn0KCnB1YmxpYyBzdGF0aWMgaW50IHJlY3Vyc2lvbkFsZyhpbnRbXVtdYXJyLGludCBjb3VudCxpbnQgeCwgaW50IHksIGludCBtYXhfeSwgU3RyaW5nW10gcm91dGUsIGludCBpKQp7CiAgICBpZiAoeCA9PSAwICYmIHkgPT0gbWF4X3kpIHtyZXR1cm4gY291bnQ7fQogICAgZWxzZSBpZiAoeCA9PSAwKSB7CiAgICAgICAgcm91dGVbaV09IlJpZ2h0IjsKICAgICAgICByZXR1cm4gcmVjdXJzaW9uQWxnKGFycixjb3VudCthcnJbeF1beSsxXSx4LHkrMSxtYXhfeSxyb3V0ZSxpKzEpOwogICAgfQogICAgZWxzZSBpZiAoeT09bWF4X3kpewogICAgICAgIHJvdXRlW2ldPSJVcCI7CiAgICAgICAgcmV0dXJuIHJlY3Vyc2lvbkFsZyhhcnIsY291bnQrYXJyW3gtMV1beV0seC0xLHksbWF4X3kscm91dGUsaSsxKTsKICAgIH0gICAgIAogICAgZWxzZSBpZiAocmVjdXJzaW9uQWxnKGFycixjb3VudCthcnJbeC0xXVt5XSx4LTEseSxtYXhfeSxyb3V0ZSxpKzEpPnJlY3Vyc2lvbkFsZyhhcnIsY291bnQrYXJyW3hdW3krMV0seCx5KzEsbWF4X3kscm91dGUsaSsxKSkKICAgIHsKICAgICAgICByb3V0ZVtpXT0iVXAiOwogICAgICAgIHJldHVybiAgcmVjdXJzaW9uQWxnKGFycixjb3VudCthcnJbeC0xXVt5XSx4LTEseSxtYXhfeSxyb3V0ZSxpKzEpOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIHJvdXRlW2ldPSJSaWdodCI7CiAgICAgICAgcmV0dXJuIHJlY3Vyc2lvbkFsZyhhcnIsY291bnQrYXJyW3hdW3krMV0seCx5KzEsbWF4X3kscm91dGUsaSsxKTsKICAgIH0KfQoKcHVibGljIHN0YXRpYyB2b2lkIHByaW50Um91dGVBcnJheShTdHJpbmdbXSBhcnIpCnsKICAgIGludCBpPTA7CiAgICB3aGlsZSAoaTxhcnIubGVuZ3RoICYmIGFycltpXSE9bnVsbCkKICAgIHsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50KGFycltpXSsiLS0+Iik7CiAgICAgICAgaSsrOwogICAgfQogICAgU3lzdGVtLm91dC5wcmludGxuKCJFbmQiKTsKfSAgICAKfQ==