Given two integers N and M where N is the number of boxes placed in a row and M is the number of colours of diamonds which are distributed in these boxes such that each box contains at least 1 diamond in it. Each diamond has a colour and a value represented by a M * N matrix where mat[i][j] denotes number of diamonds of colour i in the jth box. The task is to take exactly one colour type diamond from each box such that the total value of the chosen diamonds is maximum and diamonds taken from adjacent boxes are of a different colour. If it is not possible to satisfy the condition then print -1.
Examples:
Input: mat[][] = {
{10, 2, 20, 0},
{0, 0, 5, 0},
{0, 0, 0, 6},
{4, 0, 11, 5},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}}
Output: 23
Explanation: From box 1, we can choose either 10 diamonds of Colour1 or 4 diamonds of Colour4. But since from box 2, we have to choose 2 diamonds of Colour1, therefore choose 4 diamonds of Colour4 from box 1.
Similarly, to maximize the diamonds count, choose 11 diamonds of Colour4 from box 3 and 6 diamonds of Colour3 from box 4.
The total diamonds chosen = 4 + 2 + 11 + 6 = 23, which is the maximum count possible.Input: mat[][] = {
{1, 0, 0},
{0, 0, 5},
{0, 11, 5},
{0, 0, 0},
{0, 0, 0},
{0, 0, 0},
{0, 0, 0}}
Output: 16
Explanation: We choose 1 from the 1st box of Colour1, 11 from the 2nd box of Colour3, and 5 from the 3rd box of Colour2.
Approach:
- Dynamic programming can be used to solve this problem.
- Make a 2-D array of size M x N and the definition will be by choosing the ith colour of the jth column what is the maximum value that can be obtained.
- The recurrence relation will be dp[i][j] = arr[i][j] + max of (dp[1…M][i-1]).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the maximized value int maxSum(vector<vector< int > > arr) { // Number of rows and columns int m = ( int )arr.size(); int n = ( int )arr[0].size() - 1; // Creating the Dp array int dp[m][n + 1]; // memset(arr, 0, sizeof(arr)); memset (dp, 0, sizeof (dp)); // Populating the first column for ( int i = 1; i < m; ++i) dp[i][1] = arr[i][1]; for ( int i = 1; i < n + 1; ++i) { // Iterating over all the rows for ( int j = 1; j < m; ++j) { int mx = 0; // Getting the (i-1)th max value for ( int k = 1; k < m; ++k) { if (k != j) { if (dp[k][i - 1] > mx) { mx = dp[k][i - 1]; } } } // Adding it to the current cell if (mx and arr[j][i]) { dp[j][i] = arr[j][i] + mx; } } } // Getting the max sum // from the last column int ans = -1; for ( int i = 1; i <= m; ++i) { if (dp[i][n]) ans = max(ans, dp[i][n]); } return ans; } // Driver code int main() { // Columns are indexed 1-based vector<vector< int > > arr = { { 0, 0, 0, 0, 0 }, { 0, 10, 2, 20, 0 }, { 0, 0, 0, 5, 0 }, { 0, 0, 0, 0, 6 }, { 0, 4, 0, 11, 5 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } }; cout << maxSum(arr); return 0; } |
Java
// Java implementation of the approach import java.io.*; import java.util.*; class GFG{ // Function to return the maximized value static int maxSum( int [][] arr) { // Number of rows and columns int m = ( int )arr.length; int n = ( int )arr[ 0 ].length - 1 ; // Creating the Dp array int [][] dp = new int [m + 1 ][n + 2 ]; // memset(arr, 0, sizeof(arr)); for ( int i = 0 ; i <= m; i++) { for ( int j = 0 ; j <= n + 1 ; j++) { dp[i][j] = 0 ; } } // Populating the first column for ( int i = 1 ; i < m; ++i) dp[i][ 1 ] = arr[i][ 1 ]; for ( int i = 1 ; i < n + 1 ; ++i) { // Iterating over all the rows for ( int j = 1 ; j < m; ++j) { int mx = 0 ; // Getting the (i-1)th max value for ( int k = 1 ; k < m; ++k) { if (k != j) { if (dp[k][i - 1 ] > mx) { mx = dp[k][i - 1 ]; } } } // Adding it to the current cell if (mx != 0 && arr[j][i] != 0 ) { dp[j][i] = arr[j][i] + mx; } } } // Getting the max sum // from the last column int ans = - 1 ; for ( int i = 1 ; i <= m; ++i) { if ((dp[i][n]) != 0 ) ans = Math.max(ans, dp[i][n]); } return ans; } // Driver code public static void main(String[] args) { // Columns are indexed 1-based int [][] arr = { { 0 , 0 , 0 , 0 , 0 }, { 0 , 10 , 2 , 20 , 0 }, { 0 , 0 , 0 , 5 , 0 }, { 0 , 0 , 0 , 0 , 6 }, { 0 , 4 , 0 , 11 , 5 }, { 0 , 0 , 0 , 0 , 0 }, { 0 , 0 , 0 , 0 , 0 }, { 0 , 0 , 0 , 0 , 0 } }; System.out.println(maxSum(arr)); } } // This code is contributed by sanjoy_62 |
Python3
# Python 3 implementation of the approach # Function to return the maximized value def maxSum(arr): # Number of rows and columns m = len (arr) n = len (arr[ 0 ]) - 1 # Creating the Dp array dp = [[ 0 for i in range (n + 1 )] for j in range (m)] # Populating the first column for i in range ( 1 ,m, 1 ): dp[i][ 1 ] = arr[i][ 1 ] for i in range ( 1 ,n + 1 , 1 ): # Iterating over all the rows for j in range ( 1 ,m, 1 ): mx = 0 # Getting the (i-1)th max value for k in range ( 1 ,m, 1 ): if (k ! = j): if (dp[k][i - 1 ] > mx): mx = dp[k][i - 1 ] # Adding it to the current cell if (mx and arr[j][i]): dp[j][i] = arr[j][i] + mx # Getting the max sum # from the last column ans = - 1 for i in range ( 1 ,m, 1 ): if (dp[i][n]): ans = max (ans, dp[i][n]) return ans # Driver code if __name__ = = '__main__' : # Columns are indexed 1-based arr = [[ 0 , 0 , 0 , 0 , 0 ], [ 0 , 10 , 2 , 20 , 0 ], [ 0 , 0 , 0 , 5 , 0 ], [ 0 , 0 , 0 , 0 , 6 ], [ 0 , 4 , 0 , 11 , 5 ], [ 0 , 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 , 0 ]] print (maxSum(arr)) # This code is contributed by bgangwar59. |
C#
// C# implementation of the approach using System; public class GFG { // Function to return the maximized value static int maxSum( int [,] arr) { // Number of rows and columns int m = ( int )arr.GetLength(0); int n = ( int )arr.GetLength(1) - 1; // Creating the Dp array int [,] dp = new int [m + 1,n + 2]; // memset(arr, 0, sizeof(arr)); for ( int i = 0; i <= m; i++) { for ( int j = 0; j <= n + 1; j++) { dp[i,j] = 0; } } // Populating the first column for ( int i = 1; i < m; ++i) dp[i,1] = arr[i,1]; for ( int i = 1; i < n + 1; ++i) { // Iterating over all the rows for ( int j = 1; j < m; ++j) { int mx = 0; // Getting the (i-1)th max value for ( int k = 1; k < m; ++k) { if (k != j) { if (dp[k,i - 1] > mx) { mx = dp[k,i - 1]; } } } // Adding it to the current cell if (mx != 0 && arr[j,i] != 0) { dp[j,i] = arr[j,i] + mx; } } } // Getting the max sum // from the last column int ans = -1; for ( int i = 1; i <= m; ++i) { if ((dp[i,n]) != 0) ans = Math.Max(ans, dp[i,n]); } return ans; } // Driver code public static void Main(String[] args) { // Columns are indexed 1-based int [,] arr = { { 0, 0, 0, 0, 0 }, { 0, 10, 2, 20, 0 }, { 0, 0, 0, 5, 0 }, { 0, 0, 0, 0, 6 }, { 0, 4, 0, 11, 5 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } }; Console.WriteLine(maxSum(arr)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript implementation of the approach // Function to return the maximized value function maxSum(arr) { // Number of rows and columns let m = arr.length; let n = arr[0].length - 1; // Creating the Dp array let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)); // Populating the first column for (let i = 1; i < m; ++i) dp[i][1] = arr[i][1]; for (let i = 1; i < n + 1; ++i) { // Iterating over all the rows for (let j = 1; j < m; ++j) { let mx = 0; // Getting the (i-1)th max value for (let k = 1; k < m; ++k) { if (k != j) { if (dp[k][i - 1] > mx) { mx = dp[k][i - 1]; } } } // Adding it to the current cell if (mx && arr[j][i]) { dp[j][i] = arr[j][i] + mx; } } } // Getting the max sum // from the last column let ans = -1; for (let i = 1; i <= m; ++i) { if (dp[i][n]) {ans = Math.max(ans, dp[i][n])}; } return ans; } // Driver code // Columns are indexed 1-based let arr = [ [0, 0, 0, 0, 0], [0, 10, 2, 20, 0], [0, 0, 0, 5, 0], [0, 0, 0, 0, 6], [0, 4, 0, 11, 5], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], ]; document.write(maxSum(arr)); // This code is contributed by gfgking. </script> |
23
Time Complexity: O(n*(m^2))
Auxiliary Space: O(n*m)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!