Maximizing Points in Grid with Disappearing Neighbours
Given a 2D array grid[][] of size N * M, the value in grid[][] represents points that you can collect, if you collect any points from a particular cell then all the points from the adjacent row (i.e, i – 1 and i + 1) and adjacent column (i.e, j + 1 and j – 1) will get disappear. The task is to collect the maximum number of points from the grid.
Note: You can start collecting points from any cells in the matrix.
Examples:
Input: grid[][] = {{3, 8, 6, 9}, {9, 9, 1, 2}, {3, 9, 1, 7}}
Output: 33
Explanation: Collect points 8, 9, from row 1 and 9 and 7 from row 3.Input: grid[][] = {{12, 7, 6, 5}, {9, 9, 3, 1}, {9, 8, 1, 2}}
Output: 29
Approach (Using Dynamic Programming):
This problem can be divided into multiple smaller subproblems. The first subproblem involves finding the maximum value of points collected in each row while following the condition that no two consecutive cells in each row (i.e., grid[i][j + 1] and grid[i][j – 1]) are collected simultaneously. Store the results of this subproblem into another array and apply the same technique again to achieve the constraint that points cannot be collected from adjacent rows.
Steps to solve the problem:
- Iterate over each row of the grid and call a findMax() to find the maximum points that can be collected in each row by following the constraint that points at the adjacent column cells can’t be collected.
- Store the result of each row in an array (say dp[]).
- Again call the findMax() for the stored state in dp[], to find the maximum value that can be collected among all rows by following constraints that points 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 point // collected at ith index by following // the rule that no two consective // points 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 > >& grid) { int m = grid.size(); // This will store the maximum points // collected by each row. vector< int > dp; // Find the maximum values obtained by // each row by following the constrain // that no two consective cell // of column can't be collected for ( int i = 0; i < m; i++) { int val = findMax(grid[i]); dp.push_back(val); } // Again call the find1, as again we // have similar problem that no two // consective rows Can be collected return findMax(dp); } // Driver code int main() { vector<vector< int > > grid = { { 3, 8, 6, 9 }, { 9, 9, 1, 2 }, { 3, 9, 1, 7 } }; // Function Call int result = solve(grid); cout << result; return 0; } |
Java
import java.util.*; class MaximumPoints { // Function to find the maximum value static int findMax(ArrayList<Integer> arr) { int n = arr.size(); int result = 0 ; // Create dp of size n, where dp[i] // will store the maximum point // collected at ith index by following // the rule that no two consecutive // points can't be collected ArrayList<Integer> dp = new ArrayList<>(n); dp.add(arr.get( 0 )); result = dp.get( 0 ); if (n <= 1 ) return result; dp.add(Math.max(arr.get( 1 ), arr.get( 0 ))); result = Math.max(result, dp.get( 1 )); for ( int i = 2 ; i < n; i++) { dp.add(Math.max(dp.get(i - 1 ), arr.get(i) + dp.get(i - 2 ))); result = Math.max(result, dp.get(i)); } return result; } static int solve(ArrayList<ArrayList<Integer> > grid) { int m = grid.size(); // This will store the maximum points // collected by each row. ArrayList<Integer> dp = new ArrayList<>(); // Find the maximum values obtained by // each row by following the constraint // that no two consecutive cell // of the column can't be collected for ( int i = 0 ; i < m; i++) { int val = findMax(grid.get(i)); dp.add(val); } // Again call the findMax, as again we // have a similar problem that no two // consecutive rows can be collected return findMax(dp); } // Driver code public static void main(String[] args) { ArrayList<ArrayList<Integer> > grid = new ArrayList<>(Arrays.asList( new ArrayList<>(Arrays.asList( 3 , 8 , 6 , 9 )), new ArrayList<>(Arrays.asList( 9 , 9 , 1 , 2 )), new ArrayList<>( Arrays.asList( 3 , 9 , 1 , 7 )))); // Function Call int result = solve(grid); System.out.println(result); } } |
Python3
def find_max(arr): n = len (arr) result = 0 # Create dp of size n, where dp[i] # will store the maximum point # collected at ith index by following # the rule that no two consecutive # points 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 ]) for i in range ( 2 , n): dp[i] = max (dp[i - 1 ], arr[i] + dp[i - 2 ]) result = max (result, dp[i]) return result def solve(grid): m = len (grid) # This will store the maximum points # collected by each row. dp = [] # Find the maximum values obtained by # each row by following the constraint # that no two consecutive cells # of a column can't be collected for i in range (m): val = find_max(grid[i]) dp.append(val) # Again call the find_max, as again we # have a similar problem that no two # consecutive rows can be collected return find_max(dp) # Driver code if __name__ = = "__main__" : grid = [ [ 3 , 8 , 6 , 9 ], [ 9 , 9 , 1 , 2 ], [ 3 , 9 , 1 , 7 ] ] # Function Call result = solve(grid) print (result) # This code is contributed by shivamgupta0987654321 |
C#
using System; using System.Collections.Generic; class MaximumPointsCollection { // Function to find the maximum value static int FindMax(List< int > arr) { int n = arr.Count, result = 0; // Create dp of size n, where dp[i] // will store the maximum point // collected at ith index by following // the rule that no two consective // points can't be collected List< int > dp = new List< int >(n); dp.Add(arr[0]); result = dp[0]; if (n <= 1) return result; dp.Add(Math.Max(arr[1], arr[0])); result = Math.Max(result, dp[1]); for ( int i = 2; i < n; i++) { dp.Add(Math.Max(dp[i - 1], arr[i] + dp[i - 2])); result = Math.Max(result, dp[i]); } return result; } static int Solve(List<List< int >> grid) { int m = grid.Count; // This will store the maximum points // collected by each row. List< int > dp = new List< int >(); // Find the maximum values obtained by // each row by following the constrain // that no two consective cell // of column can't be collected for ( int i = 0; i < m; i++) { int val = FindMax(grid[i]); dp.Add(val); } // Again call the FindMax, as again we // have similar problem that no two // consective rows Can be collected return FindMax(dp); } // Driver code static void Main() { List<List< int >> grid = new List<List< int >> { new List< int > {3, 8, 6, 9}, new List< int > {9, 9, 1, 2}, new List< int > {3, 9, 1, 7} }; // Function Call int result = Solve(grid); Console.WriteLine(result); } } // This code is contributed by shivamgupta310570 |
Javascript
// Javascript code to implement the approach // Function to find the maximum value function findMax(arr) { let n = arr.length, result = 0; // Create dp of size n, where dp[i] // will store the maximum point // collected at ith index by following // the rule that no two consective // points 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; } function solve(grid) { let m = grid.length; // This will store the maximum points // collected by each row. let dp = []; // Find the maximum values obtained by // each row by following the constrain // that no two consective cell // of column can't be collected for (let i = 0; i < m; i++) { let val = findMax(grid[i]); dp.push(val); } // Again call the find1, as again we // have similar problem that no two // consective rows Can be collected return findMax(dp); } // Driver code let grid = [ [3, 8, 6, 9], [9, 9, 1, 2], [3, 9, 1, 7] ]; // Function Call let result = solve(grid); console.log(result); // This code is contributed by ragul21 |
33
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))
Contact Us