Given a 2D array arr[][] of size N * M, the value in arr[][] represents the value of coins, the task is to maximize the value of collected coins when during collecting the coins from the arr[][], all the coins from the adjacent row (i.e, i – 1 and i + 1) will disappear, and coins at the adjacent column (i.e arr[i][j + 1] and arr[i][j – 1]) will also get disappear.
Examples:
Input: arr[][] = {{2, 7, 6, 5}, {9, 9, 1, 2}, {3, 8, 1, 5}}
Output: 25
Explanation: Collect coin 7, 5, from row 1 and 8 and 5 from row 3.Input: arr[][] = {{12, 7, 6, 5}, {9, 9, 3, 1}, {9, 8, 1, 2}}
Output: 29
An approach using Dynamic programming:
This problem is composed of multiple smaller subproblems.
- First subproblem is that if we somehow know the maximum value of coins collected by each row by following the condition that no two consecutive cell in each of the rows (i.e, arr[i][j + 1] and arr[i][j – 1]) would be collected at the same time. We’ll store this subproblem in some other array and
- Again we have to follow the other constraint of the problem that coins can’t be collected in adjacent row.
And to solve this constraint we’ll again use the similar technique that we used before to find the result.
Follow the steps below to implement the above idea:
- Iterate over each row and call a recursive function (say findMax) to find the maximum coin that can be collected in each row by following the constraint that coins at the adjacent column can’t be collected.
- Store the above result in an array (say dp[]).
- Again call the findMax function for the state stored in the dp[] array, to find the maximum value that can be collected among all rows by considering that coins at adjacent rows can’t be collected.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum value int findMax(vector<int>& arr) { int n = arr.size(), result = 0; // Create dp of size n, where dp[i] // will store the maximum coin // collected at ith index by following // the rule that no two consecutive // coins can't be collected vector<int> dp(n); dp[0] = arr[0]; result = dp[0]; if (n <= 1) return result; dp[1] = max(arr[1], arr[0]); result = max(result, dp[1]); for (int i = 2; i < n; i++) { dp[i] = max(dp[i - 1], arr[i] + dp[i - 2]); result = max(result, dp[i]); } return result; } int solve(vector<vector<int> >& matrix) { int m = matrix.size(); if (m == 0) return 0; // This will store the maximum coins // collected by each row. vector<int> dp; // Find the maximum values obtained by // each row by following the constraint // that no two consecutive cell // of column can't be collected for (int i = 0; i < m; i++) { int val = findMax(matrix[i]); dp.push_back(val); } // Again call the find1, as again we // have similar problem that no two // consecutive rows Can be collected return findMax(dp); } // Driver code int main() { vector<vector<int> > arr = { { 2, 7, 6, 5 }, { 9, 9, 1, 2 }, { 3, 8, 1, 5 } }; // Function Call int result = solve(arr); cout << result; return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to find the maximum value static int findMax(int[] arr) { int n = arr.length, result = 0; // Create dp of size n, where dp[i] will store the // maximum coin collected at ith index by following // the rule that no two consecutive coins can't be // collected int[] dp = new int[n]; dp[0] = arr[0]; result = dp[0]; if (n <= 1) { return result; } dp[1] = Math.max(arr[1], arr[0]); result = Math.max(result, dp[1]); for (int i = 2; i < n; i++) { dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - 2]); result = Math.max(result, dp[i]); } return result; } static int solve(int[][] matrix) { int m = matrix.length; if (m == 0) { return 0; } // This will store the maximum coins collected by // each row. List<Integer> dp = new ArrayList<>(); // Find the maximum values obtained by each row by // following the constraint that no two consecutive // cell of column can't be collected for (int i = 0; i < m; i++) { int val = findMax(matrix[i]); dp.add(val); } // Again call the find1, as again we have similar // problem that no two consecutive rows Can be // collected return findMax(dp.stream() .mapToInt(Integer::intValue) .toArray()); } public static void main(String[] args) { int[][] arr = { { 2, 7, 6, 5 }, { 9, 9, 1, 2 }, { 3, 8, 1, 5 } }; // Function call int result = solve(arr); System.out.print(result); } } // This code is contributed by lokeshmvs21. |
Python3
import math class GFG : # Function to find the maximum value @staticmethod def findMax( arr) : n = len(arr) result = 0 # Create dp of size n, where dp[i] will store the # maximum coin collected at ith index by following # the rule that no two consecutive coins can't be # collected dp = [0] * (n) dp[0] = arr[0] result = dp[0] if (n <= 1) : return result dp[1] = max(arr[1],arr[0]) result = max(result,dp[1]) i = 2 while (i < n) : dp[i] = max(dp[i - 1],arr[i] + dp[i - 2]) result = max(result,dp[i]) i += 1 return result @staticmethod def solve( matrix) : m = len(matrix) if (m == 0) : return 0 # This will store the maximum coins collected by # each row. dp = [0] * (m) # Find the maximum values obtained by each row by # following the constraint that no two consecutive # cell of column can't be collected i = 0 while (i < m) : val = GFG.findMax(matrix[i]) dp[i] = val i += 1 # Again call the find1, as again we have similar # problem that no two consecutive rows Can be # collected return GFG.findMax(dp) @staticmethod def main( args) : arr = [[2, 7, 6, 5], [9, 9, 1, 2], [3, 8, 1, 5]] # Function call result = GFG.solve(arr) print(result, end ="") if __name__=="__main__": GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// C# code to implement the approach using System; using System.Collections; public class GFG { // Function to find the maximum value static int findMax(int[] arr) { int n = arr.Length, result = 0; // Create dp of size n, where dp[i] will store the // maximum coin collected at ith index by following // the rule that no two consecutive coins can't be // collected int[] dp = new int[n]; dp[0] = arr[0]; result = dp[0]; if (n <= 1) { return result; } dp[1] = Math.Max(arr[1], arr[0]); result = Math.Max(result, dp[1]); for (int i = 2; i < n; i++) { dp[i] = Math.Max(dp[i - 1], arr[i] + dp[i - 2]); result = Math.Max(result, dp[i]); } return result; } static int solve(int[, ] matrix) { int m = matrix.GetLength(0); if (m == 0) { return 0; } // This will store the maximum coins collected by // each row. int[] dp = new int[m]; // Find the maximum values obtained by each row by // following the constraint that no two consecutive // cell of column can't be collected for (int i = 0; i < m; i++) { int[] temp = new int[(matrix.GetLength(1))]; for (int j = 0; j < 4; j++) { temp[j] = matrix[i, j]; } int val = findMax(temp); dp[i] = val; } // Again call the find1, as again we have similar // problem that no two consecutive rows Can be // collected return findMax(dp); } static public void Main() { // Code int[, ] arr = new int[3, 4] { { 2, 7, 6, 5 }, { 9, 9, 1, 2 }, { 3, 8, 1, 5 } }; // Function call int result = solve(arr); Console.Write(result); } } // This code is contributed by lokesh. |
Javascript
<script> // JavaScript code to implement the approach // Function to find the maximum value const findMax = (arr) => { let n = arr.length, result = 0; // Create dp of size n, where dp[i] // will store the maximum coin // collected at ith index by following // the rule that no two consecutive // coins can't be collected let dp = new Array(n).fill(0); dp[0] = arr[0]; result = dp[0]; if (n <= 1) return result; dp[1] = Math.max(arr[1], arr[0]); result = Math.max(result, dp[1]); for (let i = 2; i < n; i++) { dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - 2]); result = Math.max(result, dp[i]); } return result; } const solve = (matrix) => { let m = matrix.length; if (m == 0) return 0; // This will store the maximum coins // collected by each row. let dp = []; // Find the maximum values obtained by // each row by following the constraint // that no two consecutive cell // of column can't be collected for (let i = 0; i < m; i++) { let val = findMax(matrix[i]); dp.push(val); } // Again call the find1, as again we // have similar problem that no two // consecutive rows Can be collected return findMax(dp); } // Driver code let arr = [[2, 7, 6, 5], [9, 9, 1, 2], [3, 8, 1, 5]]; // Function Call let result = solve(arr); document.write(result); // This code is contributed by rakeshsahni </script> |
Output
25
Time Complexity: O(N * M) where N is the number of rows and M is the number of columns
Auxiliary Space: O(max(N, M))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
