个人中心
gpt4 book ai didi

c++ - 找到一个 m*m (2<=m
转载 作者：行者123 更新时间：2023-11-30 17:31:14 25 4
gpt4 key购买 nike

我已经为上述问题编写了一个解决方案，但是有人可以建议一个优化的方法吗？我已经遍历了 count(2 到 n) 的数组，其中 count 正在查找大小为 count*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;

示例:

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

输出:最大总和 = 71

2 4 7 -2

4 3 9 9

5 2 6 8

5 4 3 2

最佳答案

这个问题最好使用动态编程 (DP) 或内存来解决。

假设 n 非常大，您会发现重新计算每个可能的矩阵组合的总和将花费太长时间，因此如果您可以重用以前的计算，那么一切都会变得更快。

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

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;

该算法的复杂度为:O(n*n*m*m)或更准确地说:0.5*n*(n-1)*m*(m-1)。 (现在我还没有对此进行测试，所以如果有任何错误请告诉我。)

关于c++ - 找到一个 m*m (2<=m<n) 且总和最大的子数组；从 n*n int 数组中(有 +ve、-ve、0)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24735439/

25 4 0

文章推荐： 时钟不准确
文章推荐： c - 作为值提供给 CFReadStreamSetProperty() 的对象的生命周期
文章推荐： c - 插入链表
文章推荐： c - 在c中实现异或加密时没有输出到磁盘
行者123
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com