Given three arrays A[], B[] and C[] of size N and three positive integers X, Y, and Z, the task is to find the maximum sum possible by selecting at most N array elements such that at most X elements are from the array A[], at most Y elements from the array B[], at most Z elements are from the array C[] and all elements are from different indices.
Examples:
Input: A[] = {10, 0, 5}, B[] = {5, 10, 0}, C[] = {0, 5, 10}, X = 1, Y = 1, Z = 1
Output: 30
Explanation:
Selecting A[0], B[1], C[2] makes the sum = A[0] + B[1] + C[2] = 30, which is the maximum possible sum after satisfying the given conditions.
Therefore, the required output is 30.Input: A[] = {0}, B[] = {0}, C[] = {0}, X = 1, Y = 1, Z = 1
Output: 0
Naive approach: Follow the steps below to solve the problem:
- Traverse all the arrays and generate all the possible combinations to select at most N elements from the three different arrays that satisfy the given condition:
- For every ith element, the following four operations can be performed:
- Select ith element from the array, A[].
- Select ith element from the array, A[].
- Select ith element from the array, A[].
- Select ith element from any of the arrays.
- Therefore, the recurrence relation to solving the problem is as follows:
FindMaxS(X, Y, Z, i) = max(A[i] + FindMaxS(X – 1, Y, Z, i – 1), B[i] + FindMaxS(X, Y – 1, Z, i – 1), C[i] + FindMaxS(X, Y, Z – 1, i – 1), FindMaxS(X, Y, Z, i – 1))
- Using the above recurrence relation, print the maximum sum of selecting N array elements based on the given conditions.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum sum of at most N with// different index array elements such that at most X// are from A[], Y are from B[] and Z are from C[]int FindMaxS(int X, int Y, int Z, int n, vector<int>& A, vector<int>& B, vector<int>& C){ // Base Cases if (X < 0 or Y < 0 or Z < 0) return INT_MIN; if (n < 0) return 0; // Selecting i-th element from A[] int ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C); // Selecting i-th element from B[] int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C); // Selecting i-th element from C[] int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1, A, B, C); // i-th elements not selected from // any of the arrays int no = FindMaxS(X, Y, Z, n - 1, A, B, C); // Select the maximum sum from all // the possible calls int maximum = max(ch, max(ca, max(co, no))); return maximum;}// Driver Codeint main(){ // Given X, Y and Z int X = 1; int Y = 1; int Z = 1; // Given A[] vector<int> A = { 10, 0, 5 }; // Given B[] vector<int> B = { 5, 10, 0 }; // Given C[] vector<int> C = { 0, 5, 10 }; // Given Size int n = B.size(); // Function Call cout << FindMaxS(X, Y, Z, n - 1, A, B, C);} |
Java
// Java program for the above approachclass GFG { // Function to find maximum sum of at most N with // different index array elements such that at most X // are from A[], Y are from B[] and Z are from C[] static int FindMaxS(int X, int Y, int Z, int n, int A[], int B[], int C[]) { // Base Cases if (X < 0 || Y < 0 || Z < 0) return Integer.MIN_VALUE; if (n < 0) return 0; // Selecting i-th element from A[] int ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C); // Selecting i-th element from B[] int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C); // Selecting i-th element from C[] int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1, A, B, C); // i-th elements not selected from // any of the arrays int no = FindMaxS(X, Y, Z, n - 1, A, B, C); // Select the maximum sum from all // the possible calls int maximum = Math.max(ch, Math.max(ca, Math.max(co, no))); return maximum; } // Driver Code public static void main(String[] args) { // Given X, Y and Z int X = 1; int Y = 1; int Z = 1; // Given A[] int A[] = { 10, 0, 5 }; // Given B[] int B[] = { 5, 10, 0 }; // Given C[] int C[] = { 0, 5, 10 }; // Given Size int n = B.length; // Function Call System.out.println( FindMaxS(X, Y, Z, n - 1, A, B, C)); }}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find maximum sum of at most N with# different index array elements such that at most X# are from A[], Y are from B[] and Z are from C[]def FindMaxS(X, Y, Z, n): global A, B, C if (X < 0 or Y < 0 or Z < 0): return -10**9 if (n < 0): return 0 # Selecting i-th element from A[] ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1) # Selecting i-th element from B[] ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1) # Selecting i-th element from C[] co = C[n] + FindMaxS(X, Y, Z - 1, n - 1) # i-th elements not selected from # any of the arrays no = FindMaxS(X, Y, Z, n - 1) # Select the maximum sum from all # the possible calls maximum = max(ch, max(ca, max(co, no))) return maximum# Driver Codeif __name__ == '__main__': # Given X, Y and Z X = 1 Y = 1 Z = 1 # Given A[] A = [10, 0, 5] # Given B[] B = [5, 10, 0] # Given C[] C = [0, 5, 10] # Given Size n = len(B) # Function Call print(FindMaxS(X, Y, Z, n - 1)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG { // Function to find maximum sum of at most N with // different index array elements such that at most X // are from []A, Y are from []B and Z are from C[] static int FindMaxS(int X, int Y, int Z, int n, int[] A, int[] B, int[] C) { // Base Cases if (X < 0 || Y < 0 || Z < 0) return int.MinValue; if (n < 0) return 0; // Selecting i-th element from []A int ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C); // Selecting i-th element from []B int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C); // Selecting i-th element from C[] int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1, A, B, C); // i-th elements not selected from // any of the arrays int no = FindMaxS(X, Y, Z, n - 1, A, B, C); // Select the maximum sum from all // the possible calls int maximum = Math.Max(ch, Math.Max(ca, Math.Max(co, no))); return maximum; } // Driver Code public static void Main(String[] args) { // Given X, Y and Z int X = 1; int Y = 1; int Z = 1; // Given []A int[] A = { 10, 0, 5 }; // Given []B int[] B = { 5, 10, 0 }; // Given C[] int[] C = { 0, 5, 10 }; // Given Size int n = B.Length; // Function Call Console.WriteLine( FindMaxS(X, Y, Z, n - 1, A, B, C)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach// Function to find maximum sum of at most N with// different index array elements such that at most X// are from A[], Y are from B[] and Z are from C[]function FindMaxS(X, Y, Z, n, A, B, C){ // Base Cases if (X < 0 || Y < 0 || Z < 0) return -1000000000; if (n < 0) return 0; // Selecting i-th element from A[] var ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C); // Selecting i-th element from B[] var ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C); // Selecting i-th element from C[] var co = C[n] + FindMaxS(X, Y, Z - 1, n - 1, A, B, C); // i-th elements not selected from // any of the arrays var no = FindMaxS(X, Y, Z, n - 1, A, B, C); // Select the maximum sum from all // the possible calls var maximum = Math.max(ch, Math.max(ca, Math.max(co, no))); return maximum;}// Driver Code// Given X, Y and Zvar X = 1;var Y = 1;var Z = 1;// Given A[]var A = [10, 0, 5];// Given B[]var B = [5, 10, 0];// Given C[]var C = [0, 5, 10];// Given Sizevar n = B.length;// Function Calldocument.write( FindMaxS(X, Y, Z, n - 1, A, B, C));</script> |
Output:
30
Time Complexity: O(4N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized using memoization. Follow the steps below to solve the problem:
- Initialize a 4D array, say dp[N][X][Y][Z], to store the overlapping subproblems of the above recurrence relation.
- Use the above recurrence relation and print the value of dp[N][X][Y][Z] using memoization.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Store overlapping subproblems// of the recurrence relationint dp[50][50][50][50];// Function to find maximum sum of at most N with// different index array elements such that at most X// are from A[], Y are from B[] and Z are from C[]int FindMaxS(int X, int Y, int Z, int n, vector<int>& A, vector<int>& B, vector<int>& C){ // Base Cases if (X < 0 or Y < 0 or Z < 0) return INT_MIN; if (n < 0) return 0; // If the subproblem already computed if (dp[n][X][Y][Z] != -1) { return dp[n][X][Y][Z]; } // Selecting i-th element from A[] int ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C); // Selecting i-th element from B[] int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C); // Selecting i-th element from C[] int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1, A, B, C); // i-th elements not selected from // any of the arrays int no = FindMaxS(X, Y, Z, n - 1, A, B, C); // Select the maximum sum from all // the possible calls int maximum = max(ch, max(ca, max(co, no))); return dp[n][X][Y][Z] = maximum;}// Driver Codeint main(){ // Given X, Y and Z int X = 1; int Y = 1; int Z = 1; // Given A[] vector<int> A = { 10, 0, 5 }; // Given B[] vector<int> B = { 5, 10, 0 }; // Given C[] vector<int> C = { 0, 5, 10 }; // Given Size int n = B.size(); memset(dp, -1, sizeof(dp)); // Function Call cout << FindMaxS(X, Y, Z, n - 1, A, B, C);} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Store overlapping subproblems // of the recurrence relation static int[][][][] dp = new int[50][50][50][50]; // Function to find maximum sum of at most N with // different index array elements such that at most X // are from A[], Y are from B[] and Z are from C[] static int FindMaxS(int X, int Y, int Z, int n, int[] A, int[] B, int[] C) { // Base Cases if (X < 0 || Y < 0 || Z < 0) return Integer.MIN_VALUE; if (n < 0) return 0; // If the subproblem already computed if (dp[n][X][Y][Z] != -1) { return dp[n][X][Y][Z]; } // Selecting i-th element from A[] int ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C); // Selecting i-th element from B[] int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C); // Selecting i-th element from C[] int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1, A, B, C); // i-th elements not selected from // any of the arrays int no = FindMaxS(X, Y, Z, n - 1, A, B, C); // Select the maximum sum from all // the possible calls int maximum = Math.max(ch, Math.max(ca, Math.max(co, no))); return dp[n][X][Y][Z] = maximum; } // Driver Code public static void main(String[] args) { // Given X, Y and Z int X = 1; int Y = 1; int Z = 1; // Given A[] int[] A = { 10, 0, 5 }; // Given B[] int[] B = { 5, 10, 0 }; // Given C[] int[] C = { 0, 5, 10 }; // Given Size int n = B.length; for (int i = 0; i < 50; i++) for (int j = 0; j < 50; j++) for (int k = 0; k < 50; k++) for (int l = 0; l < 50; l++) dp[i][j][k][l] = -1; // Function Call System.out.print(FindMaxS(X, Y, Z, n - 1, A, B, C)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachimport sys# Store overlapping subproblems# of the recurrence relationdp = [[[[-1 for i in range(50)] for j in range(50)] for k in range(50)] for l in range(50)]# Function to find maximum sum of at most N with# different index array elements such that at most X# are from A[], Y are from B[] and Z are from C[]def FindMaxS(X, Y, Z, n, A, B, C): # Base Cases if (X < 0 or Y < 0 or Z < 0): return -sys.maxsize - 1 if (n < 0): return 0 # If the subproblem already computed if (dp[n][X][Y][Z] != -1): return dp[n][X][Y][Z] # Selecting i-th element from A[] ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C) # Selecting i-th element from B[] ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C) # Selecting i-th element from C[] co = C[n] + FindMaxS(X, Y, Z - 1, n - 1, A, B, C) # i-th elements not selected from # any of the arrays no = FindMaxS(X, Y, Z, n - 1, A, B, C) # Select the maximum sum from all # the possible calls maximum = max(ch, max(ca, max(co, no))) dp[n][X][Y][Z] = maximum return dp[n][X][Y][Z]# Driver Codeif __name__ == '__main__': # Given X, Y and Z X = 1 Y = 1 Z = 1 # Given A[] A = [10, 0, 5] # Given B[] B = [5, 10, 0] # Given C[] C = [0, 5, 10] # Given Size n = len(B) # Function Call print(FindMaxS(X, Y, Z, n - 1, A, B, C)) # This code is contributed by bgangwar59 |
C#
// C# program for the above approachusing System;class GFG { // Store overlapping subproblems // of the recurrence relation static int[, , , ] dp = new int[50, 50, 50, 50]; // Function to find maximum sum of at most N with // different index array elements such that at most X // are from A[], Y are from B[] and Z are from C[] static int FindMaxS(int X, int Y, int Z, int n, int[] A, int[] B, int[] C) { // Base Cases if (X < 0 || Y < 0 || Z < 0) return Int32.MinValue; if (n < 0) return 0; // If the subproblem already computed if (dp[n, X, Y, Z] != -1) { return dp[n, X, Y, Z]; } // Selecting i-th element from A[] int ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C); // Selecting i-th element from B[] int ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C); // Selecting i-th element from C[] int co = C[n] + FindMaxS(X, Y, Z - 1, n - 1, A, B, C); // i-th elements not selected from // any of the arrays int no = FindMaxS(X, Y, Z, n - 1, A, B, C); // Select the maximum sum from all // the possible calls int maximum = Math.Max(ch, Math.Max(ca, Math.Max(co, no))); return dp[n, X, Y, Z] = maximum; } // Driver Code public static void Main(string[] args) { // Given X, Y and Z int X = 1; int Y = 1; int Z = 1; // Given A[] int[] A = { 10, 0, 5 }; // Given B[] int[] B = { 5, 10, 0 }; // Given C[] int[] C = { 0, 5, 10 }; // Given Size int n = B.Length; for (int i = 0; i < 50; i++) for (int j = 0; j < 50; j++) for (int k = 0; k < 50; k++) for (int l = 0; l < 50; l++) dp[i, j, k, l] = -1; // Function Call Console.Write(FindMaxS(X, Y, Z, n - 1, A, B, C)); }}// This code is contributed by chitranayal |
Javascript
<script> // JavaScript program for the above approach // Store overlapping subproblems // of the recurrence relation let dp = new Array(50); // Function to find maximum sum of at most N with // different index array elements such that at most X // are from A[], Y are from B[] and Z are from C[] function FindMaxS(X, Y, Z, n, A, B, C) { // Base Cases if (X < 0 || Y < 0 || Z < 0) return Number.MIN_VALUE; if (n < 0) return 0; // If the subproblem already computed if (dp[n][X][Y][Z] != -1) { return dp[n][X][Y][Z]; } // Selecting i-th element from A[] let ch = A[n] + FindMaxS(X - 1, Y, Z, n - 1, A, B, C); // Selecting i-th element from B[] let ca = B[n] + FindMaxS(X, Y - 1, Z, n - 1, A, B, C); // Selecting i-th element from C[] let co = C[n] + FindMaxS(X, Y, Z - 1, n - 1, A, B, C); // i-th elements not selected from // any of the arrays let no = FindMaxS(X, Y, Z, n - 1, A, B, C); // Select the maximum sum from all // the possible calls let maximum = Math.max(ch, Math.max(ca, Math.max(co, no))); dp[n][X][Y][Z] = maximum; return dp[n][X][Y][Z]; } // Given X, Y and Z let X = 1; let Y = 1; let Z = 1; // Given A[] let A = [ 10, 0, 5 ]; // Given B[] let B = [ 5, 10, 0 ]; // Given C[] let C = [ 0, 5, 10 ]; // Given Size let n = B.length; for(let i = 0; i < 50; i++) { dp[i] = new Array(50); for(let j = 0; j < 50; j++) { dp[i][j] = new Array(50); for(let k = 0; k < 50; k++) { dp[i][j][k] = new Array(50); for(let l = 0; l < 50; l++) { dp[i][j][k][l] = -1; } } } } // Function Call document.write(FindMaxS(X, Y, Z, n - 1, A, B, C));</script> |
Output:
30
Time Complexity: O(N * X * Y * Z)
Space Complexity: O(N * X * Y * Z)
Efficient approach : DP tabulation ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Implementations Steps :
- Initialize a 4D array dp of size (X+1) x (Y+1) x (Z+1) x (n+1), where dp[i][j][k][l] represents the maximum sum that can be obtained using at most i elements from A, j elements from B, k elements from C and considering the first l elements of A, B and C.
- Initialize the base cases i.e., dp[i][j][k][0] = 0 for all i, j, k.
- Iterate through the array A, B and C, and for each element, compute the maximum sum that can be obtained using that element and update the corresponding values in the dp array.
- At each iteration, update : dp[i][j][k][l] = max(A[l]+dp[i-1][j][k][l-1], B[l]+dp[i][j-1][k][l-1], C[l]+dp[i][j][k-1][l-1], dp[i][j][k][l-1])
- The final answer will be stored in dp[X][Y][Z][n].
Implementation :
C++
#include <bits/stdc++.h>using namespace std;// Function to find maximum sum of at most N with// different index array elements such that at most X// are from A[], Y are from B[] and Z are from C[]int FindMaxS(int X, int Y, int Z, int n, vector<int>& A, vector<int>& B, vector<int>& C){ // Create a 4D DP table of size (X+1) x (Y+1) x (Z+1) x // (n+1) vector<vector<vector<vector<int> > > > dp( X + 1, vector<vector<vector<int> > >( Y + 1, vector<vector<int> >( Z + 1, vector<int>(n + 1, 0)))); // Iterate over all possible values of X, Y, Z, and n for (int x = 0; x <= X; x++) { for (int y = 0; y <= Y; y++) { for (int z = 0; z <= Z; z++) { for (int i = 1; i <= n; i++) { int ch = INT_MIN, ca = INT_MIN, co = INT_MIN, no = INT_MIN; if (x > 0) ch = A[i - 1] + dp[x - 1][y][z][i - 1]; if (y > 0) ca = B[i - 1] + dp[x][y - 1][z][i - 1]; if (z > 0) co = C[i - 1] + dp[x][y][z - 1][i - 1]; no = dp[x][y][z][i - 1]; dp[x][y][z][i] = max(ch, max(ca, max(co, no))); } } } } return dp[X][Y][Z][n];}// Driver Codeint main(){ // Given X, Y and Z int X = 1; int Y = 1; int Z = 1; // Given A[] vector<int> A = { 10, 0, 5 }; // Given B[] vector<int> B = { 5, 10, 0 }; // Given C[] vector<int> C = { 0, 5, 10 }; // Given Size int n = B.size(); // Function Call cout << FindMaxS(X, Y, Z, n, A, B, C);}// this code is contributed by bhardwajji |
Java
import java.util.*;public class Main { // Function to find maximum sum of at most N with // different index array elements such that at most X // are from A[], Y are from B[] and Z are from C[] static int FindMaxS(int X, int Y, int Z, int n, List<Integer> A, List<Integer> B, List<Integer> C) { // Create a 4D DP table of size (X+1) x (Y+1) x // (Z+1) x (n+1) int[][][][] dp = new int[X + 1][Y + 1][Z + 1][n + 1]; // Iterate over all possible values of X, Y, Z, and // n for (int x = 0; x <= X; x++) { for (int y = 0; y <= Y; y++) { for (int z = 0; z <= Z; z++) { for (int i = 1; i <= n; i++) { int ch = Integer.MIN_VALUE, ca = Integer.MIN_VALUE, co = Integer.MIN_VALUE, no = Integer.MIN_VALUE; if (x > 0) ch = A.get(i - 1) + dp[x - 1][y][z][i - 1]; if (y > 0) ca = B.get(i - 1) + dp[x][y - 1][z][i - 1]; if (z > 0) co = C.get(i - 1) + dp[x][y][z - 1][i - 1]; no = dp[x][y][z][i - 1]; dp[x][y][z][i] = Math.max( ch, Math.max(ca, Math.max(co, no))); } } } } return dp[X][Y][Z][n]; } // Driver Code public static void main(String[] args) { // Given X, Y and Z int X = 1; int Y = 1; int Z = 1; // Given A[] List<Integer> A = new ArrayList<>(Arrays.asList(10, 0, 5)); // Given B[] List<Integer> B = new ArrayList<>(Arrays.asList(5, 10, 0)); // Given C[] List<Integer> C = new ArrayList<>(Arrays.asList(0, 5, 10)); // Given Size int n = B.size(); // Function Call System.out.println(FindMaxS(X, Y, Z, n, A, B, C)); }} |
Python3
import sys# Function to find maximum sum of at most N with# different index array elements such that at most X# are from A[], Y are from B[] and Z are from C[]def FindMaxS(X, Y, Z, n, A, B, C): # Create a 4D DP table of size (X+1) x (Y+1) x (Z+1) x (n+1) dp = [[[[0 for i in range(n+1)] for j in range(Z+1)] for k in range(Y+1)] for l in range(X+1)] # Iterate over all possible values of X, Y, Z, and n for x in range(X+1): for y in range(Y+1): for z in range(Z+1): for i in range(1, n+1): ch, ca, co, no = -sys.maxsize-1, -sys.maxsize-1, -sys.maxsize-1, -sys.maxsize-1 if x > 0: ch = A[i-1] + dp[x-1][y][z][i-1] if y > 0: ca = B[i-1] + dp[x][y-1][z][i-1] if z > 0: co = C[i-1] + dp[x][y][z-1][i-1] no = dp[x][y][z][i-1] dp[x][y][z][i] = max(ch, max(ca, max(co, no))) return dp[X][Y][Z][n]# Driver Codeif __name__ == '__main__': # Given X, Y and Z X = 1 Y = 1 Z = 1 # Given A[] A = [10, 0, 5] # Given B[] B = [5, 10, 0] # Given C[] C = [0, 5, 10] # Given Size n = len(B) # Function Call print(FindMaxS(X, Y, Z, n, A, B, C)) |
Javascript
// Function to find maximum sum of at most N with// different index array elements such that at most X// are from A[], Y are from B[] and Z are from C[]function FindMaxS(X, Y, Z, n, A, B, C){ // Create a 4D DP table of size (X+1) x (Y+1) x (Z+1) x (n+1) let dp = new Array(X + 1); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(Y + 1); for (let j = 0; j < dp[i].length; j++) { dp[i][j] = new Array(Z + 1); for (let k = 0; k < dp[i][j].length; k++) { dp[i][j][k] = new Array(n + 1).fill(0); } } } // Iterate over all possible values of X, Y, Z, and n for (let x = 0; x <= X; x++) { for (let y = 0; y <= Y; y++) { for (let z = 0; z <= Z; z++) { for (let i = 1; i <= n; i++) { let ch = Number.NEGATIVE_INFINITY, ca = Number.NEGATIVE_INFINITY, co = Number.NEGATIVE_INFINITY, no = Number.NEGATIVE_INFINITY; if (x > 0) { ch = A[i - 1] + dp[x - 1][y][z][i - 1]; } if (y > 0) { ca = B[i - 1] + dp[x][y - 1][z][i - 1]; } if (z > 0) { co = C[i - 1] + dp[x][y][z - 1][i - 1]; } no = dp[x][y][z][i - 1]; dp[x][y][z][i] = Math.max(ch, Math.max(ca, Math.max(co, no))); } } } } return dp[X][Y][Z][n];}// Driver Code// Given X, Y and Zlet X = 1;let Y = 1;let Z = 1;// Given A[]let A = [10, 0, 5];// Given B[]let B = [5, 10, 0];// Given C[]let C = [0, 5, 10];// Given Sizelet n = B.length;// Function Callconsole.log(FindMaxS(X, Y, Z, n, A, B, C)); |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class MainClass { public static int FindMaxS(int X, int Y, int Z, int n, List<int> A, List<int> B, List<int> C) { // Create a 4D DP table of size (X+1) x (Y+1) x // (Z+1) x (n+1) List<List<List<List<int> > > > dp = new List<List<List<List<int> > > >(); for (int i = 0; i <= X; i++) { dp.Add(new List<List<List<int> > >()); for (int j = 0; j <= Y; j++) { dp[i].Add(new List<List<int> >()); for (int k = 0; k <= Z; k++) { dp[i][j].Add(new List<int>()); for (int l = 0; l <= n; l++) { dp[i][j][k].Add(0); } } } } // Iterate over all possible values of X, Y, Z, and // n for (int x = 0; x <= X; x++) { for (int y = 0; y <= Y; y++) { for (int z = 0; z <= Z; z++) { for (int i = 1; i <= n; i++) { int ch = int.MinValue, ca = int.MinValue, co = int.MinValue, no = int.MinValue; if (x > 0) ch = A[i - 1] + dp[x - 1][y][z][i - 1]; if (y > 0) ca = B[i - 1] + dp[x][y - 1][z][i - 1]; if (z > 0) co = C[i - 1] + dp[x][y][z - 1][i - 1]; no = dp[x][y][z][i - 1]; dp[x][y][z][i] = Math.Max( ch, Math.Max(ca, Math.Max(co, no))); } } } } return dp[X][Y][Z][n]; } public static void Main(string[] args) { // Given X, Y and Z int X = 1; int Y = 1; int Z = 1; // Given A[] List<int> A = new List<int>() { 10, 0, 5 }; // Given B[] List<int> B = new List<int>() { 5, 10, 0 }; // Given C[] List<int> C = new List<int>() { 0, 5, 10 }; // Given Size int n = B.Count; // Function Call Console.WriteLine(FindMaxS(X, Y, Z, n, A, B, C)); }} |
Output
30
Time Complexity: O(N * X * Y * Z), where N is the size of the arrays and X, Y, Z is the index values as described in the problem statement
Space Complexity: O(N * X * Y * Z), space used for dp table
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!
