G(V,E)

G(V,E)

input: a triangular array T of n rows increasing in length from 1 to n

scratch = clone T[n-1]
for y = n-2 downto 0
    for x = 0 to y-1
        scratch[x] = T[y][x] + max(scratch[x], scratch[x+1])

output: scratch[0]

$refarray;
open TRIG, "input.txt";
while(<TRIG>){
$i++;
$_ =~ s/^s+//g;
$_ =~ s/s+$//g;
@num=split(/s+/);
for $j (0...$#num) {
  $refarray[$i]->[$j]=$num[$j];
}
}
close TRIG;
while($i>0){
   for $j (0...$i-2){
      if($refarray[$i]->[$j]>$refarray[$i]->[$j+1])
    {
    $refarray[$i-1]->[$j]+=$refarray[$i]->[$j];
    }
      else{
    $refarray[$i-1]->[$j]+=$refarray[$i]->[$j+1];
    }
      $total=$refarray[$i-1]->[$j]."t";
   }
$i-=1;
}
print $total;

int MaximumSum(List<List<int>> values)
{
    // Making a copy by values of all list and validating the data at same time.
    var numbers = new List<List<int>>();
    int index = 0;
    while ((index < values.Count) && (values[index] != null) && (values[index].Count == index + 1))
    {
        numbers.Add(new List<int>());
        for (int j = 0; j <= index; j++)
            numbers[index].Add(values[index][j]);
        index++;
    }
    if (index == values.Count)
    {
        /* Applying dinamic programming principles we can obtain the maximum value starting from the last row until the first one.
         * Storing only the optimum result until the specific value being analized.
         * At the end the value on the top of the triangle will be the maximum needed.
         */
        for (int row = numbers.Count - 2; row >= 0; row--)
            for (int col = 0; col <= row; col++)
                numbers[row][col] += (numbers[row + 1][col] > numbers[row + 1][col + 1]) ? numbers[row + 1][col] : numbers[row + 1][col + 1];
        return numbers[0][0];
    }
    else
    {
        throw new Exception("Invalid data");
    }
}

t=%w{
     1
    2 1
   3 2 1
  4 3 2 1
 5 4 3 2 1
1 2 3 4 5 10000
}.map &:to_i

l = []
i=1

loop do
    l.push t.slice!(0,i)
    i += 1
    break if t == []
end
trees = [0, 1].repeated_permutation(l.length-1).to_a.map! do |tree|
    [0].concat tree
end

trees.map! do |tree|
    newt = []
    tree.each_with_index do |e, i|
        newt.push tree.slice(0, i+1).inject :+
    end
    newt
end

rr = []
trees.each do |t|
    r = 0
    t.each_with_index do |v, i|
        r += l[i][v]
    end
    rr.push r
end
p rr.max

f=open("triangle.txt", "r")
triangle=eval("[["+f.read().replace(" ", ",").replace("n", "],[")[:-4]+"]]")
f.close()
for i in range(len(triangle)-2, -1, -1):
    for j in range(len(triangle[i])):
        triangle[i][j]+=max(triangle[i+1][j+1],triangle[i+1][j])
    del triangle[i+1]
print triangle[0][0]

1      (   1   )
2 3    (  2 3  )
4 5 6  ( 4 5 6 )

1    (  1  )
7 9  ( 7 9 )

t:"I"$'/:" "vs'read0`t;
{(-2_x),enlist (1_mmax[2;last x])+last -1_x}/[count[t]-1;t]
exit 0

$ time q tri.q -q
108146

real    0m0.018s
user    0m0.010s
sys     0m0.010s

// Read the sample data file, store as List<List<int>>
def triangle = getClass().
        getResource('test_sample_data.txt').        // get the file resource
        text.                                       // contents as string
        split('n').                                // split into lines
        collect { line ->                           // collect rows
            line.split().collect { it as int }      // collect columns
        }

println "Recursive: ${findLargestWeightRecursively(triangle)}"
println "Bottom up: ${findLargestWeightBottomUp(triangle)}"

def findLargestWeightRecursively(List triangle, row = 0, col = 0) {
    def current = triangle[row][col]
    if (row < triangle.size() - 1) {
        def w1 = findLargestWeightRecursively(triangle, row + 1, col)
        def w2 = findLargestWeightRecursively(triangle, row + 1, col + 1)
        return Math.max(w1, w2) + current
    } else {
        return current
    }
}

def findLargestWeightBottomUp(List triangle) {
    def weights = triangle[triangle.size() - 1].clone()
    for (int row = triangle.size() - 2; row >= 0; row--) {
        def nextRow = triangle[row]
        for (int col = 0; col < nextRow.size(); col++) {
            def largest = Math.max(weights[col], weights[col + 1])
            weights[col] = nextRow[col] + largest
        }
        weights.remove(weights.size() - 1)
    }
    return weights[0]
}

Recursive: 108146
Bottom up: 108146

package com.euler.problems;

    import java.util.*;

    public class Problem18
    {
       private static Map<Integer,List<Integer>> triangle = new HashMap<Integer,List<Integer>>();

       public static void main(String args[])
       {
         _init();
         int res = maxSum(triangle);
         System.out.println("Sum = "+res);
       }

       //max sum from top to bottom of right angled triangle
       public static int maxSum(Map<Integer,List<Integer>> triangle)
       {
         int sum = 0;
         if(triangle == null || triangle.isEmpty())
           return 0;
         int size = triangle.size();
         if(size == 1)
           return triangle.get(0).get(0);
         int i=size-2,tmp,tmp_max,max_value;
         while(i>=0)
         {
           List<Integer> current_row = new ArrayList<Integer>();
           current_row = triangle.get(i);
           for(int index=0; index<current_row.size(); index++)
           {
             tmp = current_row.get(index);
             tmp_max = tmp+triangle.get(i+1).get(index);
             max_value = tmp+triangle.get(i+1).get(index+1);
             if(tmp_max > max_value)
               max_value = tmp_max;
             current_row.set(index,max_value);
           }
           triangle.put(i,current_row);
           current_row = null;
           i--;

        }
      return triangle.get(0).get(0);
    }

    private static void _init()
    {
      List<List<Integer>> tuples = new ArrayList<List<Integer>>();
      tuples.add(Arrays.asList(75));
      tuples.add(Arrays.asList(95,64));
      tuples.add(Arrays.asList(17,47,82));
      tuples.add(Arrays.asList(18,35,87,10));
      tuples.add(Arrays.asList(20,4,82,47,65));
      tuples.add(Arrays.asList(19,1,23,75,3,34));
      tuples.add(Arrays.asList(88,2,77,73,7,63,67));
      tuples.add(Arrays.asList(99,65,4,28,6,16,70,92));
      tuples.add(Arrays.asList(41,41,26,56,83,40,80,70,33));
      tuples.add(Arrays.asList(41,48,72,33,47,32,37,16,94,29));
      tuples.add(Arrays.asList(53,71,44,65,25,43,91,52,97,51,14));
      tuples.add(Arrays.asList(70,11,33,28,77,73,17,78,39,68,17,57));
      tuples.add(Arrays.asList(91,71,52,38,17,14,91,43,58,50,27,29,48));
      tuples.add(Arrays.asList(63,66,4,68,89,53,67,30,73,16,69,87,40,31));
      tuples.add(Arrays.asList(4,62,98,27,23,9,70,98,73,93,38,53,60,4,23));
      int i=0;
      for(List<Integer> tuple : tuples)
      {
        triangle.put(i++,tuple);
      }
      //print
      for(Integer key : triangle.keySet())
     {
       System.out.println(triangle.get(key));
     }
    }
   }

maximizeTree tree
    | length tree == 1 = head . head $ tree
    | otherwise = maximizeTree (take (length tree - 2) tree ++ [zipWith (a b -> maximum a + b) (pairUpList . last $ tree) (tree !! (length tree - 2))])
    where pairUpList list = [[list !! n, list !! (n + 1)] | n <- [0 .. (length list - 2)]]

maximizeTree [[5], [9, 6], [4, 6, 8], [0, 7, 1, 5]]

from io import open
import os

def is_int(val):
    try:
        int(val)
        return True
    except:
        return False

class TriangleMaxTotal(object):
    def __init__(self, triangle_file_path):
        self.triangle_file_path = triangle_file_path
        self.max_sums = [0]

    def find_triangle_max_total(self):
        with open(self.triangle_file_path, "r") as f:
            for line in f:
                self.max_sums = self._process_line(line)

        self.max_sums.sort()
        return str(self.max_sums[-1])

    def _process_line(self, line):
        utf = line.encode('utf8')
        new_max_sums = [int(num) for num in utf.split(' ') if is_int(num)]

        # Calculate the first and last max sums
        new_max_sums[0] += self.max_sums[0]
        new_max_sums[-1] += self.max_sums[-1]

        # Calculate all of the middle max sums
        for i in range(1, (len(new_max_sums)-1)):
            val = new_max_sums[i]
            a = self.max_sums[i-1]
            b = self.max_sums[i]
            new_max_sums[i] = val + (a if a > b else b)

        return new_max_sums