找到一个m*m (2

I have written a solution for the above problem but can someone please suggest an optimized way. I have traversed through the array for count(2 to n) where count is finding subarrays of size count*count.

我已经为上面的问题写了一个解决方案，但是有人能建议一个优化的方法吗?我已经遍历了数组(2到n)，其中count正在查找大小计数的子数组。

int n = 5;      //Size of array, you may take a dynamic array as well
int a[5][5] = {{1,2,3,4,5},{2,4,7,-2,1},{4,3,9,9,1},{5,2,6,8,0},{5,4,3,2,1}};
int max = 0;
int **tempStore, size;

for(int count = 2; count < n; count++)
{
    for(int i = 0; i <= (n-count); i++)
    {
        for(int j = 0; j <= (n-count); j++)
        {
            int **temp = new int*[count]; 
            for(int i = 0; i < count; ++i) {
                temp[i] = new int[count];
            }

            for(int k = 0; k < count; k++)
            {
                for(int l = 0; l <count; l++)
                {
                    temp[k][l] = a[i+k][j+l];
                }
            }
            //printing fetched array
            int sum = 0;
            for(int k = 0; k < count; k++)
            {
                for(int l = 0; l <count; l++)
                {
                    sum += temp[k][l];
                    cout<<temp[k][l]<<" ";
                }cout<<endl;
            }cout<<"Sum = "<<sum<<endl;
            if(sum > max)
            {
                max = sum;
                size = count;
                tempStore = new int*[count]; 
                for(int i = 0; i < count; ++i) {
                    tempStore[i] = new int[count];
                }
                //Locking the max sum array
                for(int k = 0; k < count; k++)
                {
                    for(int l = 0; l <count; l++)
                    {
                        tempStore[k][l] = temp[k][l];
                    }
                }
            }
            //printing finished
            cout<<"------------------\n";
            //Clear temp memory
            for(int i = 0; i < size; ++i) {
                delete[] temp[i];
            }
            delete[] temp;
        }
    }
}

cout<<"Max sum is = "<<max<<endl;
for(int k = 0; k < size; k++)
{
    for(int l = 0; l <size; l++)
    {
        cout<<tempStore[k][l]<<" ";
    }cout<<endl;
}cout<<"-------------------------";

//Clear tempStore memory
for(int i = 0; i < size; ++i) {
    delete[] tempStore[i];
    }
delete[] tempStore;

Example:

例子:

1 2 3 4 5

1 2 3 4 5。

2 4 7 -2 1

2 4 7 -2 1。

4 3 9 9 1

4 3 9 9 1。

5 2 6 8 0

5 2 6 8 0。

5 4 3 2 1

5 4 3 2 1。

Output: Max sum is = 71

输出:Max和= 71。

2 4 7 -2

2 4 7 2

4 3 9 9

5 2 6 8

5 4 3 2

3 个解决方案

#1

This is a problem best solved using Dynamic Programming (DP) or memoization.

这是使用动态编程(DP)或memoization解决的问题。

Assuming n is significantly large, you will find that recalculating the sum of every possible combination of matrix will take too long, therefore if you could reuse previous calculations that would make everything much faster.

假设n是非常大的，你会发现重新计算矩阵的所有可能组合的和将花费太长时间，因此如果你可以重用之前的计算，那会使所有的事情变得更快。

The idea is to start with the smaller matrices and calculate sum of the larger one reusing the precalculated value of the smaller ones.

这个想法是先从较小的矩阵开始，然后计算较大的矩阵的和，再使用较小的矩阵的预计算值。

long long *sub_solutions = new long long[n*n*m];

#define at(r,c,i) sub_solutions[((i)*n + (r))*n + (c)]

// Winner:
unsigned int w_row = 0, w_col = 0, w_size = 0;

// Fill first layer:
for ( int row = 0; row < n; row++) {
    for (int col = 0; col < n; col++) {
        at(r, c, 0) = data[r][c];
        if (data[r][c] > data[w_row][w_col]) { 
            w_row = r;
            w_col = c;
        }           
    }
}

// Fill remaining layers.
for ( int size = 1; size < m; size++) {
    for ( int row = 0; row < n-size; row++) {
        for (int col = 0; col < n-size; col++) {
            long long sum = data[row+size][col+size];
            for (int i = 0; i < size; i++) {
                sum += data[row+size][col+i];
                sum += data[row+i][col+size];
            }
            sum += at(row, col, size-1); // Reuse previous solution.
            at(row, col, size) = sum;
            if (sum > at(w_row, w_col, w_size)) { // Could optimize this part if you only need the sum.
                w_row = row;
                w_col = col;
                w_size = size;
            }
        }
    }
}

// The largest sum is of the sub_matrix starting a w_row, w_col, and has dimensions w_size+1.
long long largest = at(w_row, w_col, w_size);

delete [] sub_solutions;

This algorithm has complexity: O(n*n*m*m) or more precisely: 0.5*n*(n-1)*m*(m-1). (Now I haven't tested this so please let me know if there are any bugs.)

该算法具有复杂度:O(n*n*m*m)或更精确:0.5*n*(n-1)*m*(m-1)。(现在我还没有测试过，如果有bug请告诉我。)

#2

Try this one (using naive approach, will be easier to get the idea):

试试这个(使用天真的方法，会更容易理解):

#include <iostream> 
#include<vector>
using namespace std; 
int main( )
{ 
    int n = 5; //Size of array, you may take a dynamic array as well
    int a[5][5] = 
      {{2,1,8,9,0},{2,4,7,-2,1},{5,4,3,2,1},{3,4,9,9,2},{5,2,6,8,0}};
    int sum, partsum;
    int i, j, k, m;
    sum = -999999; // presume minimum part sum 
    for (i = 0; i < n; i++) {
        partsum = 0;
        m = sizeof(a[i])/sizeof(int);
        for (j = 0; j < m; j++) {
            partsum += a[i][j];
        }
        if (partsum > sum) {
            k = i;
            sum = partsum;
        }
    }
    // print subarray having largest sum
    m = sizeof(a[k])/sizeof(int); // m needs to be recomputed
    for (j = 0; j < m - 1; j++) {
        cout << a[k][j] << ", ";
    }
    cout << a[k][m - 1] <<"\nmax part sum = " << sum << endl;
    return 0;
}

#3

With a cumulative sum, you may compute partial sum in constant time

有了累积和，你可以在常数时间内计算出部分和。

std::vector<std::vector<int>>
compute_cumulative(const std::vector<std::vector<int>>& m)
{
    std::vector<std::vector<int>> res(m.size() + 1, std::vector<int>(m.size() + 1));

    for (std::size_t i = 0; i != m.size(); ++i) {
        for (std::size_t j = 0; j != m.size(); ++j) {
            res[i + 1][j + 1] = m[i][j] - res[i][j]
                        + res[i + 1][j] + res[i][j + 1];
        }
    }
    return res;
}

int compute_partial_sum(const std::vector<std::vector<int>>& cumulative, std::size_t i, std::size_t j, std::size_t size)
{
    return cumulative[i][j] + cumulative[i + size][j + size]
           - cumulative[i][j + size] - cumulative[i + size][j];

}

live example

生活的例子

#1