原文：
给定一个n x n矩阵，找到一个k x k子矩阵，其中1 <= k <= n，这样子矩阵中所有元素的总和最大。 输入矩阵可以包含零，正数和负数。
例如，考虑下面的矩阵，如果k = 3，则输出应打印用蓝色包围的子矩阵。
我们强烈建议您最小化浏览器，然后自己尝试。
一个简单的pg电子试玩链接的解决方案是考虑输入矩阵中所有可能的大小为k x k的子正方形，并找到具有最大和的子正方形。 上述pg电子试玩链接的解决方案的时间复杂度为o(n ^ 2 k ^ 2)。
我们可以在o(n^2)时间内解决此问题。 此问题主要是这个的问题的扩展。 这个想法是预处理给定的方阵。 在预处理步骤中，计算临时方阵stripsum[][]中所有大小为k x 1的垂直条的总和。 一旦我们获得了所有垂直条带的总和，我们就可以计算该行中第一个子正方形的总和作为该行中前j个条带的总和，对于剩余的子正方形，我们可以通过去除前一个子正方形的最左边的条，并添加新正方形的最右边的条，在o(1)时间中计算总和。
以下是上述想法的实现。
c
// an efficient c program to find maximum sum
// sub-square matrix
#include
using namespace std;
// size of given matrix
#define n 5
// a o(n^2) function to the maximum sum sub-
// squares of size k x k in a given square
// matrix of size n x n
void printmaxsumsub(int mat[][n], int k)
{
// k must be smaller than or equal to n
if (k > n) return;
// 1: preprocessing
// to store sums of all strips of size k x 1
int stripsum[n][n];
// go column by column
for (int j=0; j max_sum)
{
max_sum = sum;
pos = &(mat[i][0]);
}
// calculate sum of remaining squares in
// current row by removing the leftmost
// strip of previous sub-square and adding
// a new strip
for (int j=1; j max_sum)
{
max_sum = sum;
pos = &(mat[i][j]);
}
}
}
// print the result matrix
for (int i=0; i
java
// an efficient java program to find maximum sum
// sub-square matrix
// class to store the position of start of
// maximum sum in matrix
class position {
int x;
int y;
// constructor
position(int x, int y) {
this.x = x;
this.y = y;
}
// updates the position if new maximum sum
// is found
void updateposition(int x, int y) {
this.x = x;
this.y = y;
}
// returns the current value of x
int getxposition() {
return this.x;
}
// returns the current value of y
int getyposition() {
return this.y;
}
}
class gfg {
// size of given matrix
static int n;
// a o(n^2) function to the maximum sum sub-
// squares of size k x k in a given square
// matrix of size n x n
static void printmaxsumsub(int[][] mat, int k) {
// k must be smaller than or equal to n
if (k > n)
return;
// 1: preprocessing
// to store sums of all strips of size k x 1
int[][] stripsum = new int[n][n];
// go column by column
for (int j = 0; j < n; j ) {
// calculate sum of first k x 1 rectangle
// in this column
int sum = 0;
for (int i = 0; i < k; i )
sum = mat[i][j];
stripsum[0][j] = sum;
// calculate sum of remaining rectangles
for (int i = 1; i < n - k 1; i ) {
sum = (mat[i k - 1][j] - mat[i - 1][j]);
stripsum[i][j] = sum;
}
}
// max_sum stores maximum sum and its
// position in matrix
int max_sum = integer.min_value;
position pos = new position(-1, -1);
// 2: calculate sum of sub-squares using stripsum[][]
for (int i = 0; i < n - k 1; i ) {
// calculate and print sum of first subsquare
// in this row
int sum = 0;
for (int j = 0; j < k; j )
sum = stripsum[i][j];
// update max_sum and position of result
if (sum > max_sum) {
max_sum = sum;
pos.updateposition(i, 0);
}
// calculate sum of remaining squares in
// current row by removing the leftmost
// strip of previous sub-square and adding
// a new strip
for (int j = 1; j < n - k 1; j ) {
sum = (stripsum[i][j k - 1] - stripsum[i][j - 1]);
// update max_sum and position of result
if (sum > max_sum) {
max_sum = sum;
pos.updateposition(i, j);
}
}
}
// print the result matrix
for (int i = 0; i < k; i ) {
for (int j = 0; j < k; j ) {
system.out.print(mat[i pos.getxposition()][j pos.getyposition()] " ");
}
system.out.println();
}
}
// driver program to test above function
public static void main(string[] args) {
n = 5;
int[][] mat = { { 1, 1, 1, 1, 1 },
{ 2, 2, 2, 2, 2 },
{ 3, 8, 6, 7, 3 },
{ 4, 4, 4, 4, 4 },
{ 5, 5, 5, 5, 5 } };
int k = 3;
system.out.println("maximum sum 3 x 3 matrix is");
printmaxsumsub(mat, k);
}
}
// this code is contributed by vivek kumar singh
c#
// an efficient c# program to find maximum sum
// sub-square matrix
using system;
// class to store the position of start of
// maximum sum in matrix
class position
{
int x;
int y;
// constructor
public position(int x, int y)
{
this.x = x;
this.y = y;
}
// updates the position if new maximum sum
// is found
public void updateposition(int x, int y)
{
this.x = x;
this.y = y;
}
// returns the current value of x
public int getxposition()
{
return this.x;
}
// returns the current value of y
public int getyposition()
{
return this.y;
}
}
class gfg
{
// size of given matrix
static int n;
// a o(n^2) function to the maximum sum sub-
// squares of size k x k in a given square
// matrix of size n x n
static void printmaxsumsub(int[,] mat, int k)
{
// k must be smaller than or equal to n
if (k > n)
return;
// 1: preprocessing
// to store sums of all strips of size k x 1
int[,] stripsum = new int[n, n];
// go column by column
for (int j = 0; j < n; j )
{
// calculate sum of first k x 1 rectangle
// in this column
int sum = 0;
for (int i = 0; i < k; i )
sum = mat[i, j];
stripsum[0, j] = sum;
// calculate sum of remaining rectangles
for (int i = 1; i < n - k 1; i )
{
sum = (mat[i k - 1, j] -
mat[i - 1, j]);
stripsum[i, j] = sum;
}
}
// max_sum stores maximum sum and its
// position in matrix
int max_sum = int.minvalue;
position pos = new position(-1, -1);
// 2: calculate sum of sub-squares using stripsum[,]
for (int i = 0; i < n - k 1; i )
{
// calculate and print sum of first subsquare
// in this row
int sum = 0;
for (int j = 0; j < k; j )
sum = stripsum[i, j];
// update max_sum and position of result
if (sum > max_sum)
{
max_sum = sum;
pos.updateposition(i, 0);
}
// calculate sum of remaining squares in
// current row by removing the leftmost
// strip of previous sub-square and adding
// a new strip
for (int j = 1; j < n - k 1; j )
{
sum = (stripsum[i, j k - 1] -
stripsum[i, j - 1]);
// update max_sum and position of result
if (sum > max_sum)
{
max_sum = sum;
pos.updateposition(i, j);
}
}
}
// print the result matrix
for (int i = 0; i < k; i )
{
for (int j = 0; j < k; j )
{
console.write(mat[i pos.getxposition(),
j pos.getyposition()] " ");
}
console.writeline();
}
}
// driver code
public static void main(string[] args)
{
n = 5;
int[,] mat = {{ 1, 1, 1, 1, 1 },
{ 2, 2, 2, 2, 2 },
{ 3, 8, 6, 7, 3 },
{ 4, 4, 4, 4, 4 },
{ 5, 5, 5, 5, 5 }};
int k = 3;
console.writeline("maximum sum 3 x 3 matrix is");
printmaxsumsub(mat, k);
}
}
// this code is contributed by princi singh
输出：
maximum sum 3 x 3 matrix is
8 6 7
4 4 4
5 5 5
相关文章：
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
