Question

17.24. Max Submatrix

中文文档

Description

Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.

Return an array [r1, c1, r2, c2], where r1, c1 are the row number and the column number of the submatrix's upper left corner respectively, and r2, c2 are the row number of and the column number of lower right corner. If there are more than one answers, return any one of them.

Note: This problem is slightly different from the original one in the book.

Example:

Input:

[

   [-1,0],

   [0,-1]

]

Output: [0,1,0,1]

Note:

• 1 <= matrix.length, matrix[0].length <= 200

Solutions

Solution 1

class Solution:
  def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
    m, n = len(matrix), len(matrix[0])
    s = [[0] * n for _ in range(m + 1)]
    for i in range(m):
      for j in range(n):
        # 构造列前缀和
        s[i + 1][j] = s[i][j] + matrix[i][j]

    mx = matrix[0][0]
    ans = [0, 0, 0, 0]
    for i1 in range(m):
      for i2 in range(i1, m):
        nums = [0] * n
        for j in range(n):
          nums[j] = s[i2 + 1][j] - s[i1][j]

        start = 0
        f = nums[0]
        for j in range(1, n):
          if f > 0:
            f += nums[j]
          else:
            f = nums[j]
            start = j
          if f > mx:
            mx = f
            ans = [i1, start, i2, j]
    return ans

class Solution {
  public int[] getMaxMatrix(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] s = new int[m + 1][n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        s[i + 1][j] = s[i][j] + matrix[i][j];
      }
    }
    int mx = matrix[0][0];
    int[] ans = new int[] {0, 0, 0, 0};
    for (int i1 = 0; i1 < m; ++i1) {
      for (int i2 = i1; i2 < m; ++i2) {
        int[] nums = new int[n];
        for (int j = 0; j < n; ++j) {
          nums[j] = s[i2 + 1][j] - s[i1][j];
        }
        int start = 0;
        int f = nums[0];
        for (int j = 1; j < n; ++j) {
          if (f > 0) {
            f += nums[j];
          } else {
            f = nums[j];
            start = j;
          }
          if (f > mx) {
            mx = f;
            ans = new int[] {i1, start, i2, j};
          }
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> s(m + 1, vector<int>(n));
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        s[i + 1][j] = s[i][j] + matrix[i][j];
    int mx = matrix[0][0];
    vector<int> ans(4);
    for (int i1 = 0; i1 < m; ++i1) {
      for (int i2 = i1; i2 < m; ++i2) {
        vector<int> nums;
        for (int j = 0; j < n; ++j)
          nums.push_back(s[i2 + 1][j] - s[i1][j]);
        int start = 0;
        int f = nums[0];
        for (int j = 1; j < n; ++j) {
          if (f > 0)
            f += nums[j];
          else {
            f = nums[j];
            start = j;
          }
          if (f > mx) {
            mx = f;
            ans[0] = i1;
            ans[1] = start;
            ans[2] = i2;
            ans[3] = j;
          }
        }
      }
    }
    return ans;
  }
};

func getMaxMatrix(matrix [][]int) []int {
  m, n := len(matrix), len(matrix[0])
  s := make([][]int, m+1)
  for i := range s {
    s[i] = make([]int, n)
  }
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      s[i+1][j] = s[i][j] + matrix[i][j]
    }
  }
  mx := matrix[0][0]
  ans := make([]int, 4)
  for i1 := 0; i1 < m; i1++ {
    for i2 := i1; i2 < m; i2++ {
      var nums []int
      for j := 0; j < n; j++ {
        nums = append(nums, s[i2+1][j]-s[i1][j])
      }
      start := 0
      f := nums[0]
      for j := 1; j < n; j++ {
        if f > 0 {
          f += nums[j]
        } else {
          f = nums[j]
          start = j
        }
        if f > mx {
          mx = f
          ans = []int{i1, start, i2, j}
        }
      }
    }
  }
  return ans
}