Given an m by n two-dimensional array arr (1 < = n,m < = 100) of arbitrary integers, find the maximum sub-array.Maximum sub-array is defined to be the sub-array whose sum of integer elements are the maximum possible.
Explanation:
- First, calculate the vertical prefix sum for all columns (an O(n2) algorithm).
- Second, assume that the maximum sub-array will be between row a and row b, inclusive. There are only O(n2) a, b pairs such that a < b. Try each of them.
- Since we already have the vertical prefix sum for all columns, the sum of elements in arr[a..b][c] for column c can be computed in O(1) time. This allows us to imagine each column sum as if it is a single element of a one-dimensional array across all columns (one dimensional array with one row and n columns).
- There’s an O(n) algorithm to compute the maximum sub-array for a one-dimensional array, known as Kadane’s Algorithm.
- Applying the Kadane’s algorithm inside each a and b combination gives the total complexity of O(n
Read full article from Maximum Sum in 2-d array | shivanimaheshwari
No comments:
Post a Comment