Using recursion to solve the problem of maximum sequence sum of matrix

Before, my colleague asked an algorithm problem that needs a brain hole. I think it's quite interesting. The idea may bring you some inspiration. I'd like to record it here

subject

There is an n-order matrix with only 0,1 elements, and the maximum value of the sum of the sequences with the value of 1 for the continuous adjacent (horizontal or vertical, no ring) elements is obtained
Suppose we have the following matrix

Then the sequence sum of the continuous adjacent elements of this matrix is 4, 3, respectively (as shown in the figure). It can be seen that the maximum value of the sequence sum of this matrix is 4

Solving problems

To calculate the maximum value of sequence sum, we can first find out all possible sequence sums, and then take the maximum value. How to find these sequences?
First of all, we found that the starting point and the end point of each sequence must be 1. We can traverse every element of the matrix. If the element value is 1, then we can start looking for all sequences starting from this element as the starting point of the sequence. We know that the sequence can extend in the vertical and horizontal directions, so we can start from this element and find its top, bottom, left and right For elements with a value of 1, continue to find elements with a value of 1 at the top, bottom, left and right of the elements (recursion). If the values that meet the conditions cannot be found, the sequence will be terminated. In the process of traversal, save the elements that each sequence traverses, and then you can know the element sum of each sequence, so as to get the maximum value of the sequence sum

The words are a bit convoluted. Next, let's take finding the maximum sequence sum of the following matrices as an example to see how to find the maximum sequence sum in detail

  1. All elements with a value of 1 are traversed from left to right and from top to bottom. The first eligible element is in the upper right corner, so start with this element to find the sequence

  2. Starting from this element, find the element whose value is 1 from the top, bottom, left and right, and find that only the elements below this element meet the conditions

  3. Then start with this element to find the element with a value of 1 before and after this element, and you can see the upper part of this element
    , the value of the left element is 1, and the element on the left obviously meets the condition, while the element on the top does not meet the condition because it is the element that has been traversed in the current traversal sequence (assuming that the element on the top meets the condition, what will happen? Next, we will look for the sequence with the element on the top as the starting point, and return to the first step, falling into an infinite loop, so the next value of the element is 1 The element cannot be the element in the currently traversing sequence! This is the key to solving the problem, please pay attention
    It can be seen that the eligible elements at this time are as follows: red circle

  4. Look for the element whose top, bottom, left and right are all 1. You can see that the element whose bottom, left and right are all 1. According to the analysis in the previous step, the right element is the element that has been traversed in the traversal sequence, so it does not meet the conditions. Then only the left and bottom elements meet the conditions

  5. Look for the element whose top, bottom, left and right are all 1 again. It can be seen that the eligible element is the red box element in step 3. Since this element is the element that has been traversed in the traversal sequence at present, it does not meet the condition. The traversal of the sequence stops here. So far, we can know that the maximum value of the sequence sum starting from the top right element is 4, connecting the traversed elements Element, as shown

    or
  6. Similarly, next, follow the above steps to traverse the remaining elements with a value of 1. It can be seen that the maximum values of the sequence and starting from these elements are 4, 3, 3, 4, respectively (as shown in the figure below)




    (the elements of the red circle represent the starting point of sequence traversal)
  7. In conclusion, the maximum value of the sequence sum of the elements whose continuous adjacent value is 1 is 4

code implementation

Now that we know how to solve the problem, let's see how to implement the code
First of all, we need to use a data structure to represent the matrix. Obviously, it is suitable to use array to represent the matrix. Here we use one-dimensional array to represent the matrix. The Java code is as follows

public class Matrix {
    /**
     * @param matrix  matrix
     * @param dimension Representative dimension matrix
     * @return Maximum value of matrix sequence
     */
    private static Integer getMaxSequetialSum(int[] matrix, int dimension) {
        int count = matrix.length;      // Number of elements of matrix
        int maxSequentialSum = 0;       // Maximum value of matrix sequence
        // Traverse elements one by one
        for (int index = 0; index < count; index++) {
            int elementValue = matrix[index];
            // If the current element is 1, find the maximum value of the sum of the sequence starting from this element
            if (elementValue == 1) {
                // Record the traversal element positions of the following sequence starting with the element marked index to prevent the element from being traversed repeatedly
                Set<Integer> traverseElementSet = new HashSet<>();
                traverseElementSet.add(index);
                // The following values are the maximum values of the sequence starting with the elements of index
                int currentSequetialSum = getCurrentVerticeSequetialSum(matrix, traverseElementSet, index, dimension);
                maxSequentialSum = Math.max(maxSequentialSum, currentSequetialSum);
            }
        }
        return maxSequentialSum;
    }

    /**
     * @param matrix  matrix
     * @param traverseElementSet The location of traversed elements in the sequence
     * @param index     Location of element, starting point of sequence
     * @param dimension dimension Order matrix
     * @return The maximum value of the sequence starting from the element with position index
     */
    private static Integer getCurrentVerticeSequetialSum(int[] matrix, Set<Integer> traverseElementSet, int index, int dimension) {
        // Find the corresponding positions of the upper, lower, left and right elements of the index element in the matrix
        int left = index - 1;
        int right = index + 1;
        int up = index - dimension;
        int down = index + dimension;

        // The value of the sequence starting with the left element
        int leftIndexSum = 0;

        // The value of the sequence starting with the right element
        int rightIndexSum = 0;

        // The value of the sequence starting from the above element
        int upIndexSum = 0;

        // The value of the sequence starting from
        int downIndexSum = 0;

        /**
         * The following four if else are designed to check the validity of the location of each element, and the value must be 1
         * Note that the element cannot be a sequence traversed element!
         * If the upper, lower, left and right elements are illegal, the sequence is terminated, and the elements and
         */

        if (left >= 0 && matrix[left] == 1 && !traverseElementSet.contains(left)) {
            Set<Integer> leftTraverseElementSet = new HashSet<>(traverseElementSet);
            leftTraverseElementSet.add(left);
            leftIndexSum = getCurrentVerticeSequetialSum(matrix, leftTraverseElementSet, left, dimension);
        } else {
            leftIndexSum = traverseElementSet.size();
        }

        // The right element must be on the same line as the element at index
        if (right / dimension == index / dimension && matrix[right] == 1 && !traverseElementSet.contains(right)) {
            traverseElementSet.add(right);
            Set<Integer> rightTraverseElementSet = new HashSet<>(traverseElementSet);
            rightTraverseElementSet.add(right);
            rightIndexSum = getCurrentVerticeSequetialSum(matrix, rightTraverseElementSet, right, dimension);
        } else {
            rightIndexSum = traverseElementSet.size();
        }

        if (up >= 0 && matrix[up] == 1 && !traverseElementSet.contains(up)) {
            Set<Integer> upTraverseElementSet = new HashSet<>(traverseElementSet);
            upTraverseElementSet.add(up);
            upIndexSum = getCurrentVerticeSequetialSum(matrix, upTraverseElementSet, up, dimension);
        } else {
            upIndexSum = traverseElementSet.size();
        }

        if (down < matrix.length && matrix[down] == 1 && !traverseElementSet.contains(down)) {
            Set<Integer> downTraverseElementSet = new HashSet<>(traverseElementSet);
            downTraverseElementSet.add(down);
            downIndexSum = getCurrentVerticeSequetialSum(matrix, downTraverseElementSet, down, dimension);
        } else {
            downIndexSum = traverseElementSet.size();
        }

        // Find the maximum value of the sequence that starts with the element whose position is index
        return Collections.max(Arrays.asList(leftIndexSum, rightIndexSum, upIndexSum, downIndexSum));
    }

    public static void main(String[] args) {
        // Initialization matrix, assuming that this matrix is a 5 x 5 matrix
        int[] matrix1 = {
                0,0,0,0,1,
                0,0,1,1,1,
                0,0,0,1,0,
                0,0,0,0,0,
        };
        int max = Matrix.getMaxSequetialSum(matrix1, 5);
        System.out.println(max);  // Print 4

        int[] matrix2 = {
                0,0,0,0,1,
                0,0,1,1,1,
                0,0,1,1,0,
                0,0,0,0,0,
        };
        max = Matrix.getMaxSequetialSum(matrix2, 5);
        System.out.println(max);  // Print 6
    }
}

Analysis of time complexity and space complexity

Any algorithm, if we don't talk about time complexity and space complexity, is a rogue. Next, let's look at the time complexity and space complexity of the above solutions
1. First of all, the spatial complexity is O(n), because we use traverseElementSet to record the location of traversal sequence elements in the traversal process
2. Recursion is used in this problem. The complexity of time is very complex. It also tests the level of programmers. We can't see it intuitively. Let's see how to deduce it. We use f(n) to express the sequence and calculation times starting from the element of position n. from the above derivation, we can see that as long as we calculate the maximum value of the sequence and starting from the upper, lower, left and right elements of this element It's natural to know f(n). That is, calculate the sequence and times starting from position n and convert them to the times of calculating the sequence and times starting from the upper, lower, left and right elements of this element

F (n) = f (left) + F (right) + F (up) + F (down)

After careful consideration, it can be seen that the calculation times of the sequence sum starting from the four elements above and left and right are the same
Thus have
F (n) = 4f (left)
If the number of matrix elements is N, then
f(n) = 4N
Because there are n elements, the total time complexity is O(4N2), i.e. O(n2)

summary

At first glance, this problem really doesn't have a clue. It can't be easily seen to use recursive thinking to solve it like reversing binary tree, so we need to be patient to analyze and learn to decompose the problem. The decomposition ideas are as follows
To find the maximum sum of a sequence is to find the sum of all sequences ----- > to find out how to find all sequences ----- > to observe that the element at the beginning of a sequence must be 1 ----- > to think about how to find all sequences starting from this element ----- > to find all sequences starting from the element with a value of 1 above, below, left, right and then the element with a value of 1 above, below, left, right and so on is Starting point recursively looks for all sequences starting from the elements with their respective values of 1, i.e. the largest sequence sum is found after finding all sequences and

Personal wechat "geekoftaste", welcome to communicate with wechat and make progress together

Tags: Java

Posted on Tue, 05 Nov 2019 12:09:40 -0800 by cbrian