Finding the highest value route

Question

Given the data below, find the highest value route moving from bottom-left to top-right.

[{ 0, 0, 0, 6 }, 
  { 2, 0, 0, 2 }, 
  { 0, 1, 1, 1 }, 
  { 3, 0, 0, 0 }]

go can only move right (east) or up (north)
Highest value route here is 3 -> 0 -> 1 -> 1 -> 1 -> 2 ->6 = 14

How should I approach this problem. Is my approach below as pseudo-code correct?

max = 0
array = defined_array 
i = len(array)
k = 0  
def path(i,j):
total = 0
    for j in range(4):
        k = j;
        total = total + int(array[i][j])    
        if total > max:
            max = total
    return path(--i,k)

key= 3
def path(i,j):
    for i in range(i):
        for j in range(array[i]):
            total = total + array[i][j]

Please check [Which site?](https://meta.stackexchange.com/questions/129598/which-computer-science-programming-stack-exchange-do-i-post-in) for general issues. Until you have a demonstrable problem, you don't have question for Stack Overflow. You're implementing a solution to a well-documented problem. Include references to your algorithm source, the expected output for your test cases, and the actual (incorrect) output. — Prune, Sep 26 '19 at 17:15

score 1 · Accepted Answer · answered Sep 27 '19 at 06:16

I didn't get your approach at all.
This is the Simple Dynamic Programming problem.
Consider this as the 2D array Arr[4][4]

[{ 0, 0, 0, 6 }, 
  { 2, 0, 0, 2 }, 
  { 0, 1, 1, 1 }, 
  { 3, 0, 0, 0 }]

Make another dp array of 4*4

First thing you need is to initialise the base cases.
So first column and last row is our base case.
dp[0][3]=Arr[0][3];

After this for first column
dp[i][0]=dp[i+1][0]+Arr[i][0];

For last row
dp[3][i]=dp[3][i-1]+Arr[3][i];

For other values
dp[i][j]=max(dp[i][j-1],dp[i+1][j])+Arr[i][j];
We will pick maximum value.

Our dp Array will look like this where answer will be 14

[{ 5, 5, 5, 14 }, 
  { 5, 5, 5, 8 }, 
  { 3, 4, 5, 6 }, 
  { 3, 3, 3, 3 }]

score 0 · Answer 2 · answered Sep 26 '19 at 14:13

This is basically the problem of finding an optimal path (in this case: the highest value route) through a graph.

There are well-known methods to find shortest paths, such as Dijkstra's algorithm and the Bellman–Ford algorithm.

For your graph being directed and acyclic (a "DAG"), I found two discussions here and here stating that these algorithms cannot just be "reversed" from min to max for finding the longest path, but that it does work if you transform your graph inverting each weight (value) to its negative number.

See also Wikipedia article on the Longest path problem.

Finding the highest value route

2 Answers2