最大子矩阵最大子数组动态规划

旧城等待， 2022-03-15 04:16 335阅读 0赞

##  最大子矩阵 最大子数组 动态规划 ##

*  最大子矩阵问题也是动态规划中经典的一道题目（感觉自己到目前为止接触到的只是动态规划的冰山一角，区间dp、数位dp… 还是要花时间深入学习一下的），这里就先总结一下最大子矩阵问题的通用思路以及解法
 *  我们先从基础难度讲起，不直接讨论二维矩阵的情况，先来看看一维数组：
    
     *  现假设有一个一维数组 arr\[n\]，要你找出连续的一段数组元素，使其和最大
     *  例如，一个一维数组：4 -5 6 3 7 -1 8 ，通过肉眼观察， 6 3 7 -1 8 为这个数组的连续最大和。那么有什么算法能够解决这个问题呢？
 *  1、穷举（暴力）
    
        int max_sum, tmp_sum;
        for(int i = 0, i < n; i++) { 
        	for(int j = 0; j <= i; j++) { 
        		tmp_sum = 0;
        		for(int k = j; k <= i; k++) { 
        			tmp_sum += arr[k];
        		}
        		if (tmp_sum > max_sum)
        			max_sum = tmp_sum;
        	}
        }
    
     *  穷举法的思路很简单，就是列举数组 arr 的所有子集，计算每个子集的和，同时更新最大值。但该方法的时间复杂度为  O ( n 3 ) O(n^3) O(n3) ，显然在 n 较大时这方法行不通
 *  2、累加
    
        arr_sum[n + 10] = { 0};
        for(i = 1; i <= n; i++) { 
        	arr_sum[i] = arr_sum[i-1] + arr[i];
        }
        int max_sum = 0, tmp_sum;
        for(i = 1;i <= n; i++) { 
        	for(j = 0; j < i; j++) { 
        		tmp_sum = arr_sum[i] - arr_sum[j];
        		if(tmp_sum > max_sum)
        			max_sum = tmp_sum;
        	}
        }
    
     *  上述方法将时间复杂度优化到了  O ( n 2 ) O(n^2) O(n2) ，不过还可以继续优化，即使用动态规划的思想
 *  3、动态规划
    
        int get_MaxSum(int arr[], int col) { 
            int max_sum = 0, tmp = 0;
            for (int i = 0; i < col; i++) { 
                if (tmp > 0) { 
                    tmp += arr[i];
                }
                else { 
                    tmp = arr[i];
                }
                if (tmp > max_sum) { 
                    max_sum = tmp;
                }
            }
            return max_sum;
        }
 *  前面说了那么多一维数组求最大子段和的方法，这和最大子矩阵有什么关系呢？继续往下看
 *  最大子矩阵题目：给定一个 n\*m 的矩阵 A，求 A 中的一个非空子矩阵，使这个子矩阵中的元素和最大。其中，A 的子矩阵指在 A 中行和列均连续的一块，例如：
    
        Example Input
        1
        3 3
        -1 -4 3
        3 4 -1
        -5 -2 8
        Example Output
        10
        样例说明:
        	取最后一列，和为10
 *  假设我们要求的最大子矩阵是原矩阵的第 i 行到第 j 行，第 k 列到第 s 列，那么如下图所示，圈出的范围即最大子矩阵。我们将最大子矩阵的每一列各自加和，就可以得到一个一维数组：\{a\[i\]\[k\] +······+ a\[j\]\[k\], ······ , a\[i\]\[s\] +······+ a\[j\]\[s\]\}，那么现在，这就变成了一个一维数组求最大子段和的问题了！也就是说，将一个二维数组的纵向元素相加，变成一个横向上的一维数组，就能使用一维的方法来解决这个问题了
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pfX01heA_size_16_color_FFFFFF_t_70]
    
        int n, m;
        int dp[maxn][maxn], tmp_arr[maxn];
        
        int get_MaxSum(int arr[], int col) { 
            int max_sum = 0, tmp = 0;
            for (int i = 0; i < col; i++) { 
                if (tmp > 0) { 
                    tmp += arr[i];
                }
                else { 
                    tmp = arr[i];
                }
                if (tmp > max_sum) { 
                    max_sum = tmp;
                }
            }
            return max_sum;
        }
        
        void solve() { 
            int cas;
            scanf("%d", &cas);
            while (cas--) { 
                scanf("%d%d", &n, &m);
                for (int i = 0; i < n; i++) { 
                    for (int j = 0; j < m; j++) { 
                        scanf("%d", &dp[i][j]);
                    }
                }
                long long int max_sum = 0, tmp_sum;
                for (int i = 0; i < n; i++) { 
                    memset(tmp_arr, 0, sizeof(tmp_arr));
                    for (int j = i; j < n; j++) { 
                        for (int k = 0; k < m; k++) { 
                            tmp_arr[k] += dp[j][k];
                        }
                        tmp_sum = get_MaxSum(tmp_arr, m);
                        if (tmp_sum > max_sum) { 
                            max_sum = tmp_sum;
                        }
                    }
                }
                cout<<max_sum<<endl;
            }
        }
 *  这里同样也可以使用累加的方法：
    
        void solve() { 
        	int dp[maxn][maxn] = { 0};
        	int n, m, tmp;
        	scanf("%d%d", &n, &m);
        	for (int i = 1; i <= n; i++) { 
        	    for (int j = 1; j <= m; j++) { 
        	        scanf("%d", &tmp);
        	        dp[i][j] = dp[i-1][j] + tmp;
        	    }
        	}
        	int tmp_sum = 0, max_sum = -999999;
        	for (int i = 1; i <= n; i++) { 
        	    for (int j = i; j <= n; j++) { 
        	        tmp_sum = 0;
        	        for (int k = 1; k <= m; k++) { 
        	            tmp_sum += dp[j][k] - dp[i-1][k];
        	            if(tmp_sum > max_sum)
        	                max_sum = tmp_sum;
        	            if(tmp_sum < 0)
        	                tmp_sum = 0;
        	        }
        	    }
        	}
        	cout<<max_sum<<endl;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pfX01heA_size_16_color_FFFFFF_t_70]: /images/20220315/f0111503712d405086294df78a9442b1.png