fork(1) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.  
  11.  
  12. static int maxSumPath(int[][] data) {
  13.     final int length = data.length;
  14.     final int[][][] sumArr = new int[3][length][length];
  15.     for (int row = length - 1; row >= 0; row--) {
  16.         for (int col = 0; col < length; col++) {
  17.         	int val = data[row][col];
  18.         	int val2 = data[row][col] * 2;
  19.             if (row == length - 1 && col == 0) {
  20.                 sumArr[0][row][col] = val;
  21.                 sumArr[1][row][col] = val2;
  22.             } else if (row == length - 1) {
  23.                 sumArr[0][row][col] = sumArr[0][row][col - 1] + val;
  24.                 sumArr[1][row][col] = Math.max(
  25.                 	sumArr[1][row][col - 1] + val
  26.                 ,   sumArr[0][row][col - 1] + val2
  27.                 );
  28.                 sumArr[2][row][col] = Math.max(
  29.                 	sumArr[1][row][col - 1] + val2
  30.                 ,   sumArr[2][row][col - 1] + val
  31.                 );
  32.             } else if (col == 0) {
  33.                 sumArr[0][row][col] = sumArr[0][row + 1][col] + val;
  34.                 sumArr[1][row][col] = Math.max(
  35.                 	sumArr[0][row + 1][col] + val2
  36.                 ,   sumArr[1][row + 1][col] + val
  37.                 );
  38.                 sumArr[2][row][col] = Math.max(
  39.                 	sumArr[1][row + 1][col] + val2
  40.                 ,   sumArr[2][row + 1][col] + val
  41.                 );
  42.             } else {
  43.                 sumArr[0][row][col] = Math.max(
  44.                 	sumArr[0][row][col - 1], sumArr[0][row + 1][col]
  45.                 ) + data[row][col];
  46.                 sumArr[1][row][col] = Math.max(
  47.                 	Math.max(sumArr[0][row][col - 1], sumArr[0][row + 1][col]) + val2
  48.                 ,   Math.max(sumArr[1][row][col - 1], sumArr[1][row + 1][col]) + val
  49.                 );
  50.                 sumArr[2][row][col] = Math.max(
  51.                 	Math.max(sumArr[1][row][col - 1], sumArr[1][row + 1][col])+val2
  52.                 ,	Math.max(sumArr[2][row][col - 1], sumArr[2][row + 1][col])+val
  53.                 );
  54.             }
  55.         }
  56.     }
  57.     return sumArr[2][0][length - 1];
  58. }	
  59.  
  60.  
  61. 	public static void main (String[] args) throws java.lang.Exception
  62. 	{
  63. 		int[][] data = new int[][] {
  64. 			new int[] {3, 0, 2}
  65. 		,   new int[] {2, 0, 0}
  66. 		,   new int[] {0, 3, 0}
  67. 		};
  68. 		System.out.println(maxSumPath(data));
  69. 	}
  70. }
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
12
https://ideone.com/GBu9DV
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!