Maximizing Sum of Non-Consecutive Elements in Matrix in Java
Given a matrix of size N×M, where N is the number of rows and M represents the number of columns, the objective is to select integer values from the matrix so that the sum of these values is maximized. Furthermore, the constraint is imposed that no two consecutive rows can have values from the same column. In other words, if a value is selected from a column in one row, the value in the following row must be drawn from a different column.
Example:
Input:
Output: Maximum sum is: 17
Explanation:
Choose 3 from the first row.
Choose 5 from the second row.
Choose 9 from the third row.
The sum of these chosen numbers is 3 + 5 + 9 = 17, which is the proper maximum feasible sum that meets the specified restrictions.
The final output is 17.
Implementation: Using Backtracking
The provided Java code employs a backtracking technique to discover the maximum sum by examining all possible combinations of selecting elements from each row while avoiding selecting consecutive columns. The maxSum() function acts as an entry point, checking for an empty matrix and starting the backtracking process. The backtrackingMaxSum() function iteratively investigates all column options for each row, calculating the total of the chosen items. The maximum total is updated at each stage, and the process repeats until all rows have been reviewed.
FileName: MaxSum.java
public class MaxSum {
public static int maxSum(int[][] matrix) {
int n = matrix.length;
// If the matrix is empty, return 0 as there is no element.
if (n == 0) {
return 0;
}
// Start the backtracking process from the first row and no previous column selected.
return backtrackingMaxSum(matrix, 0, -1);
}
private static int backtrackingMaxSum(int[][] matrix, int row, int prevIndex) {
// If we have reached the last row, return 0 as there are no more rows to explore.
if (row == matrix.length) {
return 0;
}
int maxSum = 0;
// Iterate through the columns (3 in this case) for the current row.
for (int i = 0; i < 3; i++) {
// Avoid selecting the same column as the previous one.
if (prevIndex == -1 || i != prevIndex) {
// Calculate the current sum and recursively find the sum for the next row.
int currentSum = matrix[row][i] + backtrackingMaxSum(matrix, row + 1, i);
// Update the maximum sum.
maxSum = Math.max(maxSum, currentSum);
}
}
return maxSum;
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// Print the result of the maximum sum calculation.
System.out.println("Maximum sum is: " + maxSum(matrix));
}
}
Output:
Maximum Sum is: 17
Complexity Analysis: The code uses a backtracking approach with an exponential time complexity of O(3^n), where n is the number of rows in the matrix. The recursive call stack's depth causes the space complexity to be O(n).
Implementation: Using Greedy Approach
Step 1: Set the prevMaxIndex to -1 and totalSum to 0.
Step 2: Iterate through each row of the matrix (represented by i).
Step 3: For each row, iterate through each column (represented by j).
Check to see if j differs from the previously selected column index.
If true, update maxVal and maxIndex if the current element is larger.
Step 4: If a valid maxIndex is discovered:
To totalSum, add the maximum value.
Use the desired column index to update prevMaxIndex.
Step 5: If no valid column index is discovered in a row (maxIndex == -1), terminate
the loop.
Step 6: After processing all rows, return the totalSum.
FileName: MaxSum1.java
public class MaxSum1 {
public static int maxSum(int[][] matrix) {
int n = matrix.length;
if (n == 0) {
return 0;
}
int prevMaxIndex = -1;
int totalSum = 0;
for (int i = 0; i < n; i++) {
int maxVal = Integer.MIN_VALUE;
int maxIndex = -1;
// Find the maximum value in the current row that is not from the same column as the previous maximum
for (int j = 0; j < 3; j++) {
if (j != prevMaxIndex && matrix[i][j] > maxVal) {
maxVal = matrix[i][j];
maxIndex = j;
}
}
if (maxIndex == -1) {
// No valid index found, break or handle as needed
break;
}
// Update the total sum and the index of the selected maximum value
totalSum += maxVal;
prevMaxIndex = maxIndex;
}
return totalSum;
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// Output the maximum sum
System.out.println("Maximum Sum is: " + maxSum(matrix));
}
}
Output:
Maximum Sum is: 17
Complexity Analysis: The code has a time complexity of O(n), where n represents the number of rows in the matrix. The space complexity is O(1) since the algorithm requires a constant amount of additional space.
Implementation: Using Dynamic Programming
The MaxSum2 class includes an important method named maxSum(), which uses dynamic programming to find the largest sum of non-consecutive elements in a given 2D matrix. This method creates a dynamic programming table (dp) and iterates across the matrix to populate dp with the greatest sum from the previous row while excluding the current column. Finally, the procedure delivers the highest sum obtained in the final row of the dp table. This method minimizes duplicate calculations, resulting in an efficient solution for determining the maximum sum of non-consecutive entries in the matrix.
FileName: MaxSum2.java
public class MaxSum2 {
public static int maxSum(int[][] matrix) {
int n = matrix.length;
// Check if the matrix is empty
if (n == 0) {
return 0;
}
// Dynamic programming table to store intermediate results
int[][] dp = new int[n][3];
// Base case: initialize the first row
for (int i = 0; i < 3; i++) {
dp[0][i] = matrix[0][i];
}
// Iterate through the rest of the matrix
for (int i = 1; i < n; i++) {
for (int j = 0; j < 3; j++) {
int maxVal = 0;
// Find the maximum value from the previous row excluding the current column
for (int k = 0; k < 3; k++) {
if (j != k) {
maxVal = Math.max(maxVal, dp[i - 1][k]);
}
}
// Update the dynamic programming table with the maximum value for the current cell
dp[i][j] = maxVal + matrix[i][j];
}
}
// Return the maximum value in the last row
int maxSum = 0;
for (int i = 0; i < 3; i++) {
maxSum = Math.max(maxSum, dp[n - 1][i]);
}
return maxSum;
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// Print the result of the maximum sum calculation
System.out.println("Maximum Sum is: " + maxSum(matrix));
}
}
Output:
Maximum Sum is: 17
Complexity Analysis: The dynamic programming solution in the MaxSum1 class increases computational efficiency. The time complexity is O(n), where n is the number of rows because the algorithm only iterates through the matrix once. The additional dynamic programming table used for intermediate outcomes increases the space complexity to O(n).