We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #18: Maximum path sum I
  4. Discussions

Project Euler #18: Maximum path sum I

Sort by

recency

|

77 Discussions

|

  • chaganti_kirank1
     + 0 comments

    In C#:

    using System;

    public class MaximumPathSum1 { public static void Main(string[] args) { int t = int.Parse(Console.ReadLine());

        while (t-- > 0)
    {
        int n = int.Parse(Console.ReadLine());
        int[][] arr = new int[n][];

        // Input values for each row of the array
        for (int i = 0; i < n; i++)
        {
            arr[i] = new int[i + 1]; // Initialize the array for the current row
            string[] values = Console.ReadLine().Split(' ');
            for (int j = 0; j <= i; j++)
            {
                arr[i][j] = int.Parse(values[j]); // Input the value for the current element
            }
        }

        // Call the max function and print the result
        Console.WriteLine(Max(arr));
    }
}

public static int Max(int[][] arr)
{
    int n = arr.Length;
    int[][] dp = new int[n][];
    for (int i = 0; i < n; i++)
    {
        dp[i] = new int[i + 1];
        for (int j = 0; j <= i; j++)
        {
            dp[i][j] = -1;
        }
    }
    return Recursive(0, 0, arr, n, dp);
}

private static int Recursive(int i, int j, int[][] arr, int n, int[][] dp)
{
    if (i < 0 || i >= n || j < 0 || j >= arr[i].Length)
    {
        return 0;
    }
    if (dp[i][j] != -1)
    {
        return dp[i][j];
    }
    int down = arr[i][j] + Recursive(i + 1, j, arr, n, dp);
    int right = arr[i][j] + Recursive(i + 1, j + 1, arr, n, dp);
    return dp[i][j] = Math.Max(down, right);
}

    }

  • srikv
     + 0 comments
    # Enter your code here. Read input from STDIN. Print output to STDOUT

maxsum = [0]
def max_sum(t, l, i, lsum):
    m, n = i, i+1
    if l == len(t) - 1:
        maxsum[0] = max(maxsum[0], lsum + t[l][m], lsum + t[l][n])
        return
    max_sum(t, l + 1, m, lsum + t[l][m])
    max_sum(t, l + 1, n, lsum + t[l][n])

for _ in range(int(input())):
    triangle, lvl, maxsum[0] = [], int(input()), 0
    for i in range(lvl):
        triangle.append(list(map(int,input().split())))
    #print(triangle)
    if lvl > 1:
        max_sum(triangle, 1, 0, triangle[0][0])
    print(max(maxsum[0], triangle[0][0] ))

  • robmillersoftwa1
     + 0 comments

    I really put in some effort on this one to optimize it. LMK if you see any optimizations I could make:

    //Each non-edge node is visited at least twice so caching saves a ton of time
let triangleCache = {};
//Derived from the triangular number formula
let getRowOfIdx = idx => 
	Math.floor(-0.5 + Math.sqrt(0.25 + (2 * idx)));

let calculateMaxSum = (triangle, n=0) => {
  if (n >= triangle.length) return 0;
  if (triangleCache[n]) return triangleCache[n];
	
  let left = triangle[n] + calculateMaxSum(triangle, n + getRowOfIdx(n) + 1);
  let right = triangle[n] + calculateMaxSum(triangle, n + getRowOfIdx(n) + 2);
  triangleCache[n] = Math.max(left, right);
  return triangleCache[n];
}

function processData(input) {
    let data = input.split('\n');
    let numCases = data.shift();
    for (let i = 0; i < numCases; i++) {
      let numRows = data.shift();
      let rows = [];
      for (let j = 0; j < numRows; j++) {
        rows.push(...data.shift().split(' ').map(v => parseInt(v)));
      }
      console.log(calculateMaxSum(rows));
      triangleCache = {};
    }
}

  • robmillersoftwa1
     + 0 comments

    I really put in some effort on this one to optimize it. LMK if you see any optimizations I could make:

    //This is a depth-first algorithm, caching saves ~1/2 of the calculations
let triangleCache = {};
//Derived from the triangular number formula
let getRowOfIdx = idx => Math.floor(-0.5 + Math.sqrt(0.25 + (2 * idx)));

let calculateMaxSum = (triangle, n=0) => {
  if (n >= triangle.length) return 0;
  if (triangleCache[n]) return triangleCache[n];
	
  let left = triangle[n] + calculateMaxSum(triangle, n + getRowOfIdx(n) + 1);
  let right = triangle[n] + calculateMaxSum(triangle, n + getRowOfIdx(n) + 2);
  triangleCache[n] = Math.max(left, right);
  return triangleCache[n];
}

function processData(input) {
    let data = input.split('\n');
    let numCases = data.shift();
    for (let i = 0; i < numCases; i++) {
      let numRows = data.shift();
      let rows = [];
      for (let j = 0; j < numRows; j++) {
        rows.push(...data.shift().split(' ').map(v => parseInt(v)));
      }
      console.log(calculateMaxSum(rows));
      triangleCache = {};
    }
}

  • anubhavnegi
     + 0 comments

    Java solution 

    import java.util.Arrays;
import java.util.Scanner;

public class MaximumPathSum1 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t  = sc.nextInt();


        while (t-- > 0) {
            int n = sc.nextInt();

            // Create a 2D array to store the triangle of numbers
            int[][] arr = new int[n][];

            // Input values for each row of the array
            for (int i = 0; i < n; i++) {
                arr[i] = new int[i + 1]; // Initialize the array for the current row
                for (int j = 0; j <= i; j++) {
                    arr[i][j] = sc.nextInt(); // Input the value for the current element
                }
            }

            // Call the max function and print the result
            System.out.println(max(arr));
        }

    }

    public static int max(int[][] arr){
        int n = arr.length;
        int[][] dp = new int[n][20];
        for(int[] row: dp){
            Arrays.fill(row,-1);
        }
        return recursive(0,0,arr,n,dp);
    }

    private  static int recursive(int i, int j, int[][]arr,int n,int[][] dp){

        if(i< 0 || i>= n || j < 0 || j>= arr[i].length ){
            return 0;
        }
        if(dp[i][j] != -1){
            return dp[i][j];

        }
        int down = arr[i][j] + recursive(i + 1, j, arr, n,dp);
        int right = arr[i][j] + recursive(i + 1, j + 1, arr, n,dp);

        return dp[i][j]=Math.max(down, right);
    }
}