Project Euler #345: Max sum matrix with unique path

Question

Base point: I'm looking for help on how to use Dynamic programming to solve the following problem. My current solution is a little out of control.

Problem: find the maximum sum from an NxN matrix combining only one element from each subarray, must choose elements from each of the columns. For example: [[1,2], [3,4]] The max sum would be 5. So either matrix[0][0] + matrix[1][1] or matrix[0][1] + matrix[1][0].

Should be able to run for n = 0...30.

I wrote the following function with sub-optimal time complexity:

var perm = function (values, currentCombo = [], allPerm  = []) {
  if (values.length < 1) {
    allPerm.push(currentCombo);
    return allPerm;
  }
  for (var i = 0; i < values.length; i++) {
    var copy = values.slice(0);
    var value = copy.splice(i, 1);
    perm(copy, currentCombo.concat(value), allPerm);
  }
  return allPerm;
};

var maxSumMatrix = function(matrix){
  var n = matrix.length;
  var options = [];
  for(let i = 0; i < n; i++){
      let row = new Array(n).fill(0);
      row[i] = 1;
      options.push(row);
  }
  var paths = perm(options);
  var accumMax = null;
  for(var i = 0; i < paths.length; i++){
      var sum = null;
      for(var j = 0; j < paths[i].length; j++){
        for(var k = 0; k < paths[i][j].length; k++){
          sum += paths[i][j][k] * matrix[j][k];
        }
        if(accumMax === null || accumMax < sum){
          accumMax = sum;
        }
      }
  }
  return accumMax;
}

So "perm" finds all 0,1 permutations of solutions, then I multiply each possible solution to the input matrix and find the max answer.

Thank you!

EDIT

So for the following matrix: [[1,2,4], [2,-1,0], [2,20,6]]; The greatest sum would be 26. From: matrix[0][2] + matrix[1][0] + matrix[2][1]

Am I understanding this correctly - you have an array of arrays, and you want to find the maximum sum by selecting the largest value from each sub array and sum them together? e.g. [[1, 2], [3, 4], [5, 6]] = 12? — fubar
I don't think my understanding is correct. How did you get 5 from your example? Show the plain math separate from your code. — fubar
I just added to the original question. Sorry about that. The answer 5 is from matrix[0][1] + matrix[1][0]. — aoneto
@anoeto - if the matrix is n x n, can you show a more complicated example - e.g. 3x3 or 4x4 to show how the value should be computed. — fubar

Scott Sauyet Scott Sauyet · Accepted Answer · 2017-05-30T01:06:56

Here's how I would approach it:

const remove = (start, count, list) => {
  var result = list.slice(0);
  result.splice(start, count);
  return result;
}

const removeRow = (row, matrix) => remove(row, 1, matrix);
const removeCol = (col, matrix) => matrix.map(row => remove(col, 1, row)); 
const max = (xs) => Math.max.apply(null, xs);

const maxSum = (matrix) => matrix.length === 1 
  ? max(matrix[0]) 
  : max(matrix[0].map((col, idx) => col + maxSum(removeCol(idx, removeRow(0, matrix)))));

maxSum([
  [1, 2,  4], 
  [2, -1, 0], 
  [2, 20, 6]
]); //=> 26

This would run into recursion depth problems if you are working with very large matrices.

This makes all sorts of simplifying assumptions. They boil down to the requirement that the input is a square matrix of numbers. Bad things might happen if it isn't.

If it interests you, I did this first in Ramda, because that's how I think. (I'm one of the authors.) And then I translated it to the above.

In Ramda, it might look like this:

const removeRow = curry((row, matrix) => remove(row, 1, matrix));
const removeCol = curry((col, matrix) => map(remove(col, 1), matrix)); 
const highest = (xs) => Math.max.apply(null, xs);

const maxSum = (matrix) => matrix.length == 1 
  ? highest(matrix[0]) 
  : highest(addIndex(map)((col, idx) => col + maxSum(removeCol(idx, removeRow(0, matrix))), matrix[0]));

...which you can see on the Ramda REPL.

Project Euler #345: Max sum matrix with unique path

1 Answers