CODEWITHSUNDEEP
c#algorithmmultidimensional-array
user3501919
user3501919

Reputation:

Get Max Path Sum Recursive with huge 2d array

I have to get the max path sum of a 2d array.
I can manage to get up to 40 rows, but after the function does not return any value.
Can some one help me? 

private int GetTotal(int row, int column, int[,] triangle)
{
    if (row == 0) return triangle[row, column];

    int myValue = pyramid[row, column];
    int left = myValue + GetTotal(row - 1, column, triangle);
    int right = myValue + GetTotal(row - 1, column + 1, triangle);

    return Math.Max(left, right);
}

Upvotes: 2

Views: 1473

Answers (2)

user3501919
user3501919

Reputation:

Hi Amit this is what I have done but now is actually worse. Now the overflow happen at 25 rows, while before the editing at 40 rows.

int[] cache = new int[1000]; 
private int GetTotal(int row, int column, int[,] triangle, int[] cache)
{
    if (row == 0) return triangle[row, column];

    int myValue = triangle[row, column];
    int left = myValue + GetTotal(row - 1, column, triangle, cache);
    int right = myValue + GetTotal(row - 1, column + 1, triangle, cache);

    if (cache[row] != 0)
    return cache[row];

    cache[row] = Math.Max(left, right);
    return cache[row];
}

Upvotes: 1

amit
amit

Reputation: 178441

You are observing exponential running time for your algorithm. The algorithm runs in O(2^rows) - which is quite a large number.

Consider transforming your code into a Dynamic Programming solution, which is basically an efficient way to implement such recursions, without the need to calculate some values twice (which is the case in your code).

Simplest way to do it is top-down Dynamic Programming, also known as "memorization".
Simply add a dictionary, let's call it cache, and at the beginning of the function - check if (row,column) is in the cache. If it is - just return the already computed value.
Otherwise - compute the value, and before returning it - store it in cache.

Here is a Pseudo code based on your code. It won't compile - but it should demonstrate the issue at hand.

private long GetTotal(int row, int column, Pyramid pyramid, Dictionary<Pair<int,int>,long> cache)
{
    if (row == 0) return pyramid[row, column];
    //add a check if you already calculated for this row and column:
    Pair<int,int> p = new Pair<int,int>(row,column);
    if cache.ContainsKey(p) return cache.Get(p);

    int myValue = pyramid[row, column];
    long left = myValue + GetTotal(row - 1, column, pyramid, cache); //sending the dictionary as well...
    long right = myValue + GetTotal(row - 1, column + 1, pyramid, cache);

    long best = Math.Max(left, right);
    //before returning: store the just calculated value in the cache:
    cache.Add(p,best);
    return best;
}

Upvotes: 1

Related Questions