Implementation of 3D Kadane’s Algorithm
Idea/Working of 3D Kadane’s Algorithm:
Lets see how the 3-D Kadane’s algorithm works:
- Initializing a variable maxSum to a very small value. This will keep track of the maximum sum we’ve found so far.
- Iterate over all pairs of columns: For each pair of columns, create a 1-D array where each element is the sum of elements in the rows between those two columns.
- Apply 1-D Kadane’s algorithm: Apply the 1-D Kadane’s algorithm to this array to find the maximum subarray sum. If this sum is greater than maxSum, update maxSum.
- Repeat steps 2 and 3 for all pairs of columns.
The key insight here is that any subrectangle of the 3-D array can be represented by a pair of columns, and the sum of elements within this subrectangle is just the sum of certain elements in the 1-D array we created.
This algorithm has a time complexity of O(n4), where n is the dimension of the 3-D array. This is because there are O(n2) pairs of columns, and for each pair, we spend O(n2) time to create the 1-D array and apply the 1-D Kadane’s algorithm.
Pseudocode for 3D Kadane’s Algorithm:
The pseudocode for the 3D Kadane’s Algorithm will involve iterating through all possible subarrays within the three-dimensional space and applying the algorithm’s logic to find the maximum subarray sum. This pseudocode will highlight the key differences from the original 1D version and demonstrate the algorithm’s adaptation to handle three dimensions(M, N, O).
function findMaxSubCubeSum(matrix, M, N, O):
maxSum = -(Infinity)
for i from 0 to M:
initialize 2D temporary array temp[N][O] to store intermediate sums
for j from i to M:
for k from 0 to N:
for l from 0 to O:
temp[k][l] += matrix[j][k][l]
for k from 0 to N:
for l from k to N:
initialize temporary arrays innerTemp[O] and kadane2[O]
for m from 0 to O:
innerTemp[m] += temp[l][m]
copy innerTemp to kadane2
for m from 0 to O:
if m > 0:
kadane2[m] += kadane2[m - 1]
if kadane2[m] > maxSum:
maxSum = kadane2[m]
if kadane2[m] < 0:
kadane2[m] = 0
reset temp array to 0 for next iteration
return maxSum
Below is the implementation of 3D Kadanes algorithm:
C++
#include <cstring> #include <iostream> using namespace std; typedef long long int ll; // Function to find the maximum sum of a sub-cube in a 3D // array static ll findMaxSubCubeSum( int matrix[30][30][30], int M, int N, int O) { // Initialize the maximum sum to the smallest possible // integer ll maxSum = -(1LL << 60); // Iterate over the first dimension of the 3D array for ( int i = 0; i < M; ++i) { // Initialize a 2D temporary array to store // intermediate sums ll temp[30][30]; memset (temp, 0, sizeof temp); // Iterate over the first dimension again for ( int j = i; j < M; ++j) { // Iterate over the second and third dimensions for ( int k = 0; k < N; ++k) { for ( int l = 0; l < O; ++l) { // Add the current element to the // temporary array temp[k][l] += matrix[j][k][l]; } } // Iterate over the second dimension for ( int k = 0; k < N; ++k) { // Initialize another temporary array to // store intermediate sums ll innerTemp[30], kadane2[30]; memset (innerTemp, 0, sizeof innerTemp); // Iterate over the second dimension again for ( int l = k; l < N; ++l) { // Iterate over the third dimension for ( int m = 0; m < O; ++m) { // Add the current element to the // inner temporary array innerTemp[m] += temp[l][m]; } // Copy the inner temporary array to // another array memcpy (kadane2, innerTemp, sizeof innerTemp); for ( int m = 0; m < O; ++m) { // If not the first element, add the // previous element to the current // element if (m > 0) kadane2[m] += kadane2[m - 1]; // If the current element is greater // than the maximum sum, update the // maximum sum if (kadane2[m] > maxSum) maxSum = kadane2[m]; // If the current element is less // than 0, set it to 0 if (kadane2[m] < 0) kadane2[m] = 0; } } } } } // Return the maximum sum return maxSum; } int main() { // Example inputs const int M = 3, N = 3, O = 3; int matrix[30][30][30] = { { { -1, -2, 3 }, { -4, -5, 6 }, { 7, 8, 9 } }, { { -9, -8, 7 }, { -6, -5, 4 }, { 3, 2, 1 } }, { { -1, -3, 5 }, { -7, -9, 2 }, { 4, 6, 8 } } }; // Call the function to find the maximum sum of a // sub-cube in the 3D array ll result = findMaxSubCubeSum(matrix, M, N, O); // Output the result cout << "The maximum sum of a sub-cube in the 3D array " "is: " << result << '\n' ; return 0; } |
Java
import java.util.Arrays; public class MaxSubCubeSum { // Function to find the maximum sum of a sub-cube in a 3D array static long findMaxSubCubeSum( int [][][] matrix, int M, int N, int O) { // Initialize the maximum sum to the smallest possible integer long maxSum = Long.MIN_VALUE; // Iterate over the first dimension of the 3D array for ( int i = 0 ; i < M; ++i) { // Initialize a 2D temporary array to store intermediate sums long [][] temp = new long [N][O]; // Iterate over the first dimension again for ( int j = i; j < M; ++j) { // Iterate over the second and third dimensions for ( int k = 0 ; k < N; ++k) { for ( int l = 0 ; l < O; ++l) { // Add the current element to the temporary array temp[k][l] += matrix[j][k][l]; } } // Iterate over the second dimension for ( int k = 0 ; k < N; ++k) { // Initialize another temporary array to store intermediate sums long [] innerTemp = new long [O]; long [] kadane2 = new long [O]; Arrays.fill(innerTemp, 0 ); // Iterate over the second dimension again for ( int l = k; l < N; ++l) { // Iterate over the third dimension for ( int m = 0 ; m < O; ++m) { // Add the current element to the inner temporary array innerTemp[m] += temp[l][m]; } // Apply Kadane's algorithm to find the maximum sum in the 1D array System.arraycopy(innerTemp, 0 , kadane2, 0 , O); for ( int m = 0 ; m < O; ++m) { // If not the first element, add the previous element to the current element if (m > 0 ) kadane2[m] += kadane2[m - 1 ]; // If the current element is greater than the maximum sum, update the maximum sum if (kadane2[m] > maxSum) maxSum = kadane2[m]; // If the current element is less than 0, set it to 0 if (kadane2[m] < 0 ) kadane2[m] = 0 ; } } } } } // Return the maximum sum return maxSum; } public static void main(String[] args) { // Example inputs final int M = 3 , N = 3 , O = 3 ; int [][][] matrix = { {{- 1 , - 2 , 3 }, {- 4 , - 5 , 6 }, { 7 , 8 , 9 }}, {{- 9 , - 8 , 7 }, {- 6 , - 5 , 4 }, { 3 , 2 , 1 }}, {{- 1 , - 3 , 5 }, {- 7 , - 9 , 2 }, { 4 , 6 , 8 }} }; // Call the function to find the maximum sum of a // sub-cube in the 3D array long result = findMaxSubCubeSum(matrix, M, N, O); // Output the result System.out.println( "The maximum sum of a sub-cube in the 3D array is: " + result); } } |
C#
using System; class GFG { private static long FindMaxSubCubeSum( int [,,] matrix, int M, int N, int O) { long maxSum = long .MinValue; // Iterate over the first dimension of the 3D array for ( int i = 0; i < M; ++i) { long [,] temp = new long [N, O]; for ( int j = i; j < M; ++j) { for ( int k = 0; k < N; ++k) { for ( int l = 0; l < O; ++l) { temp[k, l] += matrix[j, k, l]; } } for ( int k = 0; k < N; ++k) { long [] innerTemp = new long [O]; long [] kadane2 = new long [O]; for ( int l = k; l < N; ++l) { for ( int m = 0; m < O; ++m) { innerTemp[m] += temp[l, m]; } Array.Copy(innerTemp, kadane2, O); for ( int m = 0; m < O; ++m) { if (m > 0) kadane2[m] += kadane2[m - 1]; maxSum = Math.Max(maxSum, kadane2[m]); if (kadane2[m] < 0) kadane2[m] = 0; } } } } } return maxSum; } static void Main( string [] args) { int M = 3, N = 3, O = 3; int [,,] matrix = new int [,,] { { { -1, -2, 3 }, { -4, -5, 6 }, { 7, 8, 9 } }, { { -9, -8, 7 }, { -6, -5, 4 }, { 3, 2, 1 } }, { { -1, -3, 5 }, { -7, -9, 2 }, { 4, 6, 8 } } }; long result = FindMaxSubCubeSum(matrix, M, N, O); Console.WriteLine( "The maximum sum of a sub-cube in the 3D array is: " + result); } } |
Javascript
<script> function findMaxSubCubeSum(matrix, M, N, O) { let maxSum = Number.MIN_SAFE_INTEGER; for (let i = 0; i < M; ++i) { let temp = Array.from({ length: N }, () => new Array(O).fill(0)); for (let j = i; j < M; ++j) { for (let k = 0; k < N; ++k) { for (let l = 0; l < O; ++l) { temp[k][l] += matrix[j][k][l]; } } for (let k = 0; k < N; ++k) { let innerTemp = new Array(O).fill(0); let kadane2 = new Array(O).fill(0); for (let l = k; l < N; ++l) { for (let m = 0; m < O; ++m) { innerTemp[m] += temp[l][m]; } for (let m = 0; m < O; ++m) { kadane2[m] = innerTemp[m]; if (m > 0) { kadane2[m] += kadane2[m - 1]; } maxSum = Math.max(maxSum, kadane2[m]); if (kadane2[m] < 0) { kadane2[m] = 0; } } } } } } return maxSum; } // Example const M = 3, N = 3, O = 3; let matrix = [ [[-1, -2, 3], [-4, -5, 6], [7, 8, 9]], [[-9, -8, 7], [-6, -5, 4], [3, 2, 1]], [[-1, -3, 5], [-7, -9, 2], [4, 6, 8]] ]; let result = findMaxSubCubeSum(matrix, M, N, O); console.log( "The maximum sum of a sub-cube in the 3D array is: " + result); </script> |
Python3
# Python Implementation def findMaxSubCubeSum(matrix, M, N, O): # Initialize the maximum sum to the smallest possible integer maxSum = - ( 1 << 60 ) # Iterate over the first dimension of the 3D array for i in range (M): # Initialize a 2D temporary array to store intermediate sums temp = [[ 0 ] * N for _ in range (N)] # Iterate over the first dimension again for j in range (i, M): # Iterate over the second and third dimensions for k in range (N): for l in range (O): # Add the current element to the temporary array temp[k][l] + = matrix[j][k][l] # Iterate over the second dimension for k in range (N): # Initialize another temporary array to store intermediate sums innerTemp = [ 0 ] * O kadane2 = [ 0 ] * O # Iterate over the second dimension again for l in range (k, N): # Iterate over the third dimension for m in range (O): # Add the current element to the inner temporary array innerTemp[m] + = temp[l][m] # Copy the inner temporary array to another array kadane2 = innerTemp[:] for m in range (O): # If not the first element, add the previous element to the current element if m > 0 : kadane2[m] + = kadane2[m - 1 ] # If the current element is greater than the maximum sum, update the maximum sum if kadane2[m] > maxSum: maxSum = kadane2[m] # If the current element is less than 0, set it to 0 if kadane2[m] < 0 : kadane2[m] = 0 # Return the maximum sum return maxSum # Example inputs M = 3 N = 3 O = 3 matrix = [ [[ - 1 , - 2 , 3 ], [ - 4 , - 5 , 6 ], [ 7 , 8 , 9 ]], [[ - 9 , - 8 , 7 ], [ - 6 , - 5 , 4 ], [ 3 , 2 , 1 ]], [[ - 1 , - 3 , 5 ], [ - 7 , - 9 , 2 ], [ 4 , 6 , 8 ]] ] # Call the function to find the maximum sum of a sub-cube in the 3D array result = findMaxSubCubeSum(matrix, M, N, O) # Output the result print ( "The maximum sum of a sub-cube in the 3D array is:" , result) # This code is contributed by Tapesh(tapeshdu420) |
The maximum sum of a sub-cube in the 3D array is: 48
Time Complexity: O(M^2 * N * O), where M, N, and O are the dimensions of the 3D array.
- Outer Loop (i): The outer loop runs from 0 to M, contributing O(M) iterations.
- Middle Loop (j): The middle loop runs from i to M, contributing O(M) iterations on average.
- Inner Loops (k and l): The innermost loops iterate over the second and third dimensions, contributing O(N * O) operations.
- Considering all nested loops, the overall time complexity is O(M^2 * N * O).
Auxiliary Space: O(N * O), due to the use of the temporary arrays temp[30][30], innerTemp[30], and kadane2[30]. These arrays are of constant size and do not depend on the input size.