Maximum Plus Sum In a Matrix | Dynamic Programming Tutorials | Part 19

Hello guys, welcome back to “code with asharam”. This is part 19 of my dynamic programming tutorials. Last day I was solving May Lunchtime 2018 and I came across a beautiful problem – PLUS. Today, I am going to discuss its brute force and dynamic programming solution. If at any moment it feels like that things are going over your head, then, I advice you to read all the last last tutorials. Even after that if you are stuck somewhere, then, feel free to leave a comment. I will be more than happy to help you. So, without any further delay, let’s take a dive into deep oceans of dynamic programming.

Maximum Plus Sum

You are given with a N*M matrix arr of integers and the task is to find the maximum sum of plus shape possible. The plus(+) shape pattern is formed by taking any element with co-ordinate (x, y) as a center and then expanding it in all four directions(if possible). A plus(+) shape has atleast five elements which are { (x-1, y), (x, y-1), (x, y), (x+1, y), (x, y+1) } i.e. the arms should have length>1 but not necessarily need to have same length.

Give it a try on your own before moving forward

Brute Force Solution

You just have to traverse each element of the matrix and find the maximum plus sum possible when each element is treated as centre of plus. Finding maximum plus sum for an element as centre will take O(N+M) time and since, we have N*M elements, the time complexity of this algorithm will be O(N*M*(N+M)). Though this is not much bad like other problems involving dynamic programming but still this is not good also. Let’s see how we can improve upon this time complexity:

Dynamic Programming Solution

As I always tell you that our way of solving problems using dynamic programming is an universal constant. We will play our of game of guessing what is happening, what can or what cannot happen if we know something. Let’s make few basic observations which can be made just by carefully reading the problem:

  1. Consider a plus with centre at (i, j). You can see that its left, right, up and down branch are independent of each other. And since we want to maximise plus sum, we have to maximise the sum of left, right, up and down branch. If we denote maximum up branch sum for a starting index (i, j) as up up(i, j) and do the same for other branches, then, following algorithm can be written:
    maxPlusSum(i, j) = arr[i][j] + right(i+1, j) + up(i, j-1) + left(i-1, j) + down(i, j+1)
    
  2. Now, we just need to find right(i, j) as other branch’s function are similar to this. Since, we want the right branch sum starting at (i, j) to be maximum, hence, the right branch sum starting at (i+1, j) should be maximum. What I want to say can be represented algorithmically as follows:
    right(i, j) = arr[i][j] + right(i+1, j)

    But wait! there is one more condition possible which is to just include arr[i][j] while calculating right(i, j). Hence, we have to take the maximum of 2 conditions.

    right(i, j) = max( arr[i][j], arr[i][j] + right(i+1, j) )

    The fancy name for this recursive relation is kadane’s algorithm.

One thing to worry about is base cases of right(i, j). Clearly, you can see that if i>N, then, right(i, j) = 0. Now, we just have to write similar relations for up, down, and left branches to complete our algorithm. Let’s see how our final algorithm looks like:

right(i, j) = 0 if i > N
              max(arr[i][j], arr[i][j]+right(i+1, j)) otherwise

left(i, j) = 0 if 1 > i
             max(arr[i][j], arr[i][j]+left(i-1, j)) otherwise

up(i, j) = 0 if 1 > j
           max(arr[i][j], arr[i][j]+up(i, j-1)) otherwise

down(i, j) = 0 if j > M
             max(arr[i][j], arr[i][j]+down(i, j+1)) otherwise

maxPlusSum(i, j) = arr[i][j] + right(i+1, j) + up(i, j-1) + left(i-1, j) + down(i, j+1)

finalAnswer = max( maxPlusSum(i, j) ) where i in 1 to N and j in 1 to M

Pre-computations and code

As you can see that we need to compute right(), left(), up(), down() everytime we compute maxPlusSum(). When you unfold recursion tree of above relations, you will see that all of these relations are exponential due to problem of overlapping subproblems. Hence, we will use 4 arrays of size N*M to store pre-computed values of right(), left(), up(), down() and then, use the ached values wherever required. Let’s see how our final algorithm looks like:

Initialize:- rightDP[N][M], leftDP[N][M], upDP[N][M], downDP[N][M]

right(i, j) = 0 if i > N
              rightDP[i][j] if already computed
              rightDP[i][j] = max(arr[i][j], arr[i][j]+right(i+1, j)) otherwise

left(i, j) = 0 if 1 > i
             leftDP[i][j] if already computed
             leftDP[i][j] = max(arr[i][j], arr[i][j]+left(i-1, j)) otherwise

up(i, j) = 0 if 1 > j
           upDP[i][j] if already computed
           upDP[i][j] = max(arr[i][j], arr[i][j]+up(i, j-1)) otherwise

down(i, j) = 0 if j > M
             downDP[i][j] if already computed
             downDP[i][j] = max(arr[i][j], arr[i][j]+down(i, j+1)) otherwise

maxPlusSum(i, j) = arr[i][j] + rightDP[i+1][j] + upDP[i][j-1] + leftDP[i-1][j] + downDP[i][j+1]

finalAnswer = max( maxPlusSum(i, j) ) where i in 1 to N and j in 1 to M

Below is the beautiful code for this beautiful algorithm:

 

#include <bits/stdc++.h>
using namespace std;

#define MAX 1001

// declare

int rightDP[MAX][MAX], leftDP[MAX][MAX], 
    upDP[MAX][MAX], downDP[MAX][MAX],arr[MAX][MAX];


// compute maxPlusSum()
int maxPlusSum(int i, int j)
{
    return arr[i][j] + rightDP[i+1][j] + 
            upDP[i][j-1] + leftDP[i-1][j] + downDP[i][j+1];
}

// compute right()
int right(int i, int j, int N)
{
    if (i>N) return 0;
    else if (rightDP[i][j] != -1*INT_MAX) return rightDP[i][j];
    else return rightDP[i][j] = max(arr[i][j], arr[i][j]+right(i+1, j, N));
}

// compute left()
int left(int i, int j, int N)
{
    if (i<1) return 0;
    else if (leftDP[i][j] != -1*INT_MAX) return leftDP[i][j];
    else return leftDP[i][j] = max(arr[i][j], arr[i][j]+left(i-1, j, N));
}

// compute up()
int up(int i, int j, int M)
{
    if (j<1) return 0;
    else if (upDP[i][j] != -1*INT_MAX) return upDP[i][j];
    else return upDP[i][j] = max(arr[i][j], arr[i][j]+up(i, j-1, M));
}

//compute down()
int down(int i, int j, int M)
{
    if (j>M) return 0;
    else if (downDP[i][j] != -1*INT_MAX) return downDP[i][j];
    else return downDP[i][j] = max(arr[i][j], arr[i][j]+down(i, j+1, M));
}



int main()
{
    int N = 3, M = 4;
    arr[1][1] = 1, arr[1][2] = 1, arr[1][3] = 1, arr[1][4] = 1,
    arr[2][1] = -6, arr[2][2] = 1, arr[2][3] = 1, arr[2][4] = -4,
    arr[3][1] = 1, arr[3][2] = 1, arr[3][3] = 1, arr[3][4] = 1;

    // initalize all the dp arrays
    for (int i=0; i<MAX; i++)
    {
        for (int j=0; j<MAX; j++)
        {
            rightDP[i][j] =  -1*INT_MAX;
            leftDP[i][j] = -1*INT_MAX;
            upDP[i][j] = -1*INT_MAX;
            downDP[i][j] = -1*INT_MAX;
        }
    }

    
    for (int i=1; i<=N; i++)
    {
        for (int j=1; j<=M; j++)
        {
            right(i, j, N);
            left(i, j, N);
            up(i, j, M);
            down(i, j, M);
        }
    }

    int finalAns = -1*INT_MAX;

    // Note that centre of square cannot be on 
    // boundary of matrix
    for (int i=2; i<N; i++)
    {
        for (int j=2; j<M; j++)
        {
            finalAns = max(finalAns, maxPlusSum(i, j));
        }
    }

    cout << finalAns << endl;

    // output is 0
    
    return 0;
}

Finally we have solve Maximum plus sum with time and space complexity O(n2).
So, that’s it guys for today. I hope you would have found this tutorial insightful. If you like reading my tutorials, then, please follow my blog and share it with your friends. Meanwhile, don’t forget to solve this problem on codechef and other problems of same contest.
You can subscribe to my YouTube channel for video tutorials on dynamic programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: