3D Kadane's Algorithm - GeeksforGeeks

What is Kadane’s Algorithm?

Kadane’s algorithm is a dynamic programming technique used to find the maximum subarray sum within a one-dimensional array. It efficiently computes the maximum sum of a contiguous subarray, and its simplicity and effectiveness make it a popular choice for solving related problems.

Idea/Working of Kadane’s Algorithm:

The idea of Kadane’s algorithm is to maintain a variable max_ending_here that stores the maximum sum contiguous subarray ending at current index and a variable max_so_far stores the maximum sum of contiguous subarray found so far, Everytime there is a positive-sum value in max_ending_here compare it with max_so_far and update max_so_far if it is greater than max_so_far.

Lets take the example: {-2, -3, 4, -1, -2, 1, 5, -3}

Note: in the image max_so_far is represented by Max_Sum and max_ending_here by Curr_Sum

Here’s the step-by-step process of Kadane’s Algorithm:

• Initialize two variables, max_so_far and max_ending_here, to the first element of the array.
• Iterate over the array from the second element to the end:
• Calculate the maximum sum ending at the current position: max_ending_here = max(arr[i], max_ending_here + arr[i])
• Update max_so_far to be the maximum of max_so_far and max_ending_here: max_so_far = max(max_so_far, max_ending_here)
• Return max_so_far, which is the maximum sum of any subarray in the array.

What is 3D Kadane’s Algorithm (Extending Kadane’s Algorithm from 1D to 3D)?

As shown above, kadanes’s algorithm can be used to find contiguous sub array with maximum sum in a 1D array. This idea can be extended towards 2D as well as 3D arrays where we can find Contiguous rectangles and Contiguous Cubes respectively.

Extending Kadane’s Algorithm from 1D to 3D involves adapting the original algorithm to handle three-dimensional arrays. Extending this algorithm to 3D opens up new possibilities for solving problems related to three-dimensional data structures, such as cubes, matrices, and other spatial datasets.

Implementation of 3D Kadane’s Algorithm:

Idea/Working of 3D Kadane’s Algorithm:

Lets see how the 3-D Kadane’s algorithm works:

1. Initializing a variable maxSum to a very small value. This will keep track of the maximum sum we’ve found so far.
2. 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.
3. 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.
4. 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

Step by step algorithm:

• Initialize maxSum to the smallest possible integer.
• Iterate over the first dimension of the 3D array (i from 0 to M-1).
  • Initialize a 2D temporary array temp[30][30] to store intermediate sums.
  • Iterate over the first dimension again (j from i to M-1).
    • Iterate over the second and third dimensions (k from 0 to N-1 and l from 0 to O-1).
      • Add the current element to temp[k][l].
    • Iterate over the second dimension (k from 0 to N-1).
      • Initialize another temporary array innerTemp[30] to store intermediate sums.
      • Iterate over the second dimension again (l from k to N-1).
        • Iterate over the third dimension (m from 0 to O-1).
          • Add the current element to innerTemp[m].
    • Copy innerTemp to another array kadane2[30].
    • Iterate over the third dimension again (m from 0 to O-1).
      • If not the first element, add the previous element to the current element.
      • If kadane2[m] is greater than maxSum, update maxSum.
      • If kadane2[m] is less than 0, set it to 0.
• Return maxSum as the maximum sum of a sub-cube in the 3D array.

Below is the implementation of 3D Kadanes algorithm:

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.

3D Kadane’s Algorithm VS Brute-Force Approach

Brute Force Approach for maximum sum in 3D matrix:

Approach:

• Enumerates all possible sub-cubes in the 3D array.
• Computes the sum of each sub-cube.
• Tracks the maximum sum over all sub-cubes.

Advantages:

• Simplicity: The brute-force approach is conceptually simple. It involves straightforward nested loops to consider all possible sub-cubes.
• General Applicability: It can be applied to any type of 3D array, regardless of the values.

Disadvantages:

• Inefficiency: The time complexity is exponential, O(M^2 * N^2 * O^2), making it highly inefficient for large arrays.
• Redundancy: Involves redundant computations as it considers overlapping sub-cubes, leading to inefficient calculations.

3D Kadane’s Algorithm for maximum sum in 3D matrix:

Approach:

• Utilizes dynamic programming to efficiently compute the maximum sum.
• Uses Kadane’s algorithm for 1D and 2D arrays to find the maximum sum along each dimension.
• Iterates over the dimensions and maintains temporary arrays to store intermediate results, avoiding redundant computations.

Advantages:

• Efficiency: The algorithm has a time complexity of O(M^2 * N * O), where M, N, and O are the dimensions of the 3D array. This is more efficient than a naive approach, especially for large arrays.
• Optimization: Kadane’s algorithm optimally handles negative values and efficiently updates the maximum sum as it traverses the array.

Disadvantages:

• Complexity: The algorithm involves complex nested loops and temporary arrays, making it more complex than a brute-force approach.
• Limited Applicability: While efficient, Kadane’s algorithm is specifically designed for arrays with negative values and may not be necessary for arrays with non-negative values.

Summary:

• 3D Kadane’s Algorithm: Efficient for large arrays with negative values, but complex due to dynamic programming and temporary arrays.
• Brute Force Approach: Simple but highly inefficient for larger arrays, making it impractical in practice.

Commit to GfG's Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.