Max Sum Without Adjacent Elements | Dynamic Programming | InterviewBit Solution | C++ | Java |

 

Given a 2 x N grid of integer, A, choose numbers such that the sum of the numbers is maximum and no two chosen numbers are adjacent horizontally, vertically or diagonally, and return it.

Note: You can choose more than 2 numbers.

Input Format:

The first and the only argument of input contains a 2d matrix,  A.

Output Format:

Return an integer, representing the maximum possible sum.

Constraints:

• 1 <= N <= 20000
• 1 <= A[i] <= 2000

Example:

Input 1:

    A = [ [1]

            [2] ]

Output 1:

    2

Explanation 1:

    We will choose 2.

Input 2:

    A = [   [1, 2, 3, 4]

            [2, 3, 4, 5]    ]    

Output 2:

    We will choose 3 and 5.

Approach:

Very much similar to LIS (Longest Increasing Subsequence) but in this case dp[i] stores max  A[0][i], A[1][i] + max(dp[i-2], dp[i-3]) (of course if (i - 3) >= 0 and (i-2) >= 0) because we can't leave more than two blanks in between while choosing.

Problem Solution in C++ Programming Language:

code:

int Solution::adjacent(vector<vector<int> > &A) 

{

    int n=A[0].size();

    vector<int> dp(n,0);

    

    dp[0] =max(A[0][0],A[1][0]);

    int sol=dp[0];

    for(int i=1;i<n;i++)

    {

        dp[i]= max(A[0][i],A[1][i]);

        int k=dp[i];

        if(i-2>=0) {

            dp[i] = max(dp[i],k+ dp[i-2]);

        }if(i-3>=0)

        {

            dp[i]=max(dp[i],k+dp[i-3]);

        }

        sol= max(sol,dp[i]);

    }

    return sol;

}

Problem Solution in Java Programming Language:

code:

public class Solution {

    public int adjacent(ArrayList<ArrayList<Integer>> A) {

        int incl = Math.max(A.get(0).get(0),A.get(1).get(0));

        int excl = 0;

        int temp;

        for(int i=1; i<A.get(0).size(); i++) {

            temp = incl;

            incl = Math.max(incl, excl + 

                   Math.max(A.get(0).get(i),A.get(1).get(i)));

            excl = temp;

        }

        return incl;

    }

}

Thank you for reading.

For any questions, feedback and query comment below.

Keep coding!.