CODEWITHSUNDEEP
calgorithmdata-structuresmax
george.zrs
george.zrs

Reputation: 151

Find the optimal path from an array of positive integers, such that the sum is max

So given an array of positive integers, with n rows and m lines, I should find an algorithm that finds the path from the top of the array to the bottom of the array, so that the sum of the path is maximized. From any given point of that array, I can move downwards in 3 ways. Directly downwards, right-downwards and left-downwards. The array can also fold. That means that a left-downwards move that leads outside of the array (the cell is left at the array), can actually happen, but it leads to the left-downwards cell at the start of the array. The same happens if the cell is at the end of the array. I am given two example photos: enter image description here

The left array has a max sum of 44, and the right a max sum of 49. There are 3 possibles ways for me to go about this.

  1. Recursion
  2. Recursion with memorization
  3. Dynamic data structures.

I started trying to complete the task by creating a tree. But I don't know if this will work. Can anyone suggest anything and/or give me a code snippet of how to start? (preferably in C)

Upvotes: 0

Views: 208

Answers (3)

Jean-Marc Volle
Jean-Marc Volle

Reputation: 3333

Here is a C implementation using recursive function calling. It does not support the case where 2 position (down, downleft downright) might have the exact same value.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

const int W = 4; /*Widht of the array */
const int H = 4; /*height of the array */
#define MIN(a,b) (((a)<(b))?(a):(b))

/*recursive function finding best next position */
int *next_pos(const int * start, const int *pos, int *sum,int **path)
{
    /* evaluate next possible movement with wrapping around borders */
    const int *d = pos + W; /*down */
    const int *dr = MIN(d + 1,start + W*H-1); /*down right */
    const int *dl = d - 1; /*down lef*/
    if (d >= start + W*H )
    {
        /*we reached the end of the array time to stop */
        return NULL;
    }
    const int* next = NULL;
    /*Note if some path are equivalent (ie dr == dl) then the complexity
    increases as another level shall be tested */
    if (*d > *dr)
    {
        if (*d > *dl)
            next = d;
        else
            next = dl;
    }
    else
    {
        if (*dr>*dl )    
            next = dr;
        else
            next = dl;
    }
    assert (next != NULL); /* equivalent path have been met but not resolved */
    *sum += *next;
    *path = next; /*store path */
    path ++;
    return next_pos(start,next,sum,path);

}

int main()
{
    
    int array[W*H];
    
    /* init array with random data*/
    int i;
    for (i=0;i<W*H;i++)
    {
        if (i % W == 0)
            printf("\n");

        array[i] = rand() % 10;
        printf ("%d ",array[i]);
    }
    printf("\n");
    int start_pos = 0;
    int max = 0;
    for (i=0;i<W;i++)
    {
        /* look for highest value on first row */
        if (array[i] > max)
        {
            max = array[i];
            start_pos = i;
        }
        
    }
    printf("start position %d (%d)\n",start_pos,array[start_pos]);
    int sum = array[start_pos];
    int *path[H]; /*path max depth is H */
    path[0]=&array[start_pos];
    next_pos(&array[0], &array[start_pos], &sum,&path[1]);
    
    /* print best path (addresses can be reverted back to x,y positions if needed*/
    printf ("best path sum:%d\n",sum);
    int j;
    for (j=0;j<H;j++)
    {
        printf("%d\n",*path[j]);
    }
    
    return 0;
}

Upvotes: 1

Eric Postpischil
Eric Postpischil

Reputation: 222846

Start at the second row from the bottom. In each cell x of that row, check which of the three cells available in the next row below is greatest. Add that cell’s value to the value of the current cell x. Now each cell in that row is labeled with the total value of the best path from it to the bottom.

Repeat the above with the third row from the bottom. This will result in each cell in that row being labeled with the total value of the best path from it to the bottom.

Repeat with the fourth row from the bottom and so on until you process the top row. Then each cell in the top row has the total value from it to the bottom.

The posted question does not say where one can start. For example, is it only in the top-left corner, or can it be any cell? Regardless, once the array is adjusted as above, you can pick the cell with the greatest value from the allowed cells.

Upvotes: 0

amit
amit

Reputation: 178451

This can be easily reduced to the problem of finding longest path in a Directed Acyclic Graph.

It can be solved with dynamic programming, by trying the 3 options available from each location:

let l_x = (x-1 + n) % n  // basically, "left" but that allows to go the other side
let r_x = (x+1) % n // similar to above, but crossing from right
DP[x][y] = DP[x][y] + max { DP[l_x][y-1], DP[x][y-1], DP[r_x][y-1] }

When done, the answer is DP[n-1][m-1]

Upvotes: 0

Related Questions