最年夜子矩陣成績實例解析。本站提示廣大學習愛好者：（最年夜子矩陣成績實例解析）文章只能為提供參考，不一定能成為您想要的結果。以下是最年夜子矩陣成績實例解析正文
成績：
求一個M*N的矩陣的最年夜子矩陣和。
好比在以下這個矩陣中：
0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
具有最年夜和的子矩陣為：
9 2 -4 1 -1 8
其和為15。
思緒：
起首，這個子矩陣可所以隨意率性年夜小的，並且肇端點也能夠在任何處所，所以，要把最年夜子矩陣找出來，我們要斟酌多種情形。
假定原始矩陣的行數為M，那末關於子矩陣，它的行數可所以1到M的任何一個數，並且，關於一個K行（K < M）的子矩陣，它的第一行可所以原始矩陣的第1行到 M - K + 1 的隨意率性一行。
例子：
關於下面的矩陣，假如子矩陣的行數是2，那末它可所以上面幾個矩陣的子矩陣：
0 -2 -7 0 9 2 -6 2
或許
9 2 -6 2 -4 1 -4 1
或許
-4 1 -4 1 -1 8 0 -2
在每種情形裡（我們這裡有三種），我們還要找出一個最年夜的子矩陣，固然，這只是一種情形的最年夜子矩陣（部分最年夜），紛歧定是global最年夜。然則，假如我們曉得每種情形的最年夜，要找出global最年夜，那就小菜一碟兒了。
在講在一個特別情形下求最年夜子矩陣之前，先講一個現實：
假定這個最年夜子矩陣的維數是一維，要找出最年夜子矩陣, 道理與求“最年夜子段和成績” 是一樣的。最年夜子段和成績的遞推公式是 b[j]=max{b[j-1]+a[j], a[j]}，b[j] 指的是從0開端到j的最年夜子段和。
Java完成示例：
假定原始矩陣為：[9， 2， -6， 2]， 那末b[] = {9, 11, 5, 7}, 那末最年夜字段和為11， 假如找最年夜子矩陣的話，那末這個子矩陣是 [9， 2]
求最年夜子段和的代碼以下：
public int maxSubsequence(int[] array) {
if (array.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int[] maxSub = new int[array.length];
maxSub[0] = array[0];
for (int i = 1; i < array.length; i++) {
maxSub[i] = (maxSub[i-1] > 0) ? (maxSub[i-1] + array[i]) : array[i];
if (max < maxSub[i]) {
max = maxSub[i];
}
}
return max;
}
然則，原始矩陣可所以二維的。假定原始矩陣是一個3 * n 的矩陣，那末它的子矩陣可所以 1 * k, 2 * k, 3 * k，（1 <= k <= n）。 假如是1*K，這裡有3種情形：子矩陣在第一行，子矩陣在第二行，子矩陣在第三行。假如是 2 * k，這裡有兩種情形，子矩陣在第1、二行，子矩陣在第2、三行。假如是3 * k，只要一種情形。
為了可以或許找出最年夜的子矩陣，我們須要斟酌一切的情形。假定這個子矩陣是 2 *k, 也就是說它只要兩行，要找出最年夜子矩陣，我們要從左到右赓續的遍歷能力找出在這類情形下的最年夜子矩陣。假如我們把這兩行高低相加，情形就和求“最年夜子段和成績” 又是一樣的了。
為了找出在原始矩陣裡的最年夜子矩陣，我們要遍歷一切的子矩陣的能夠情形，也就是說，我們要斟酌這個子矩陣有能夠只要1行，2行，。。。到n行。而在每種情形下，我們都要把它所對應的矩陣部門高低相加才求最年夜子矩陣（部分）。
好比，假定子矩陣是一個3*k的矩陣，並且，它的一行是原始矩陣的第二行，那末，我們就要在
9 2 -6 2 -4 1 -4 1 -1 8 0 -2
裡找最年夜的子矩陣。
假如把它高低相加，我們就釀成了 4, 11, -10,1， 從這個數列裡可以看出，在這類情形下，最年夜子矩陣是一個3*2的矩陣，最年夜和是15.
為了可以或許在原始矩陣裡很快獲得從 i 行到 j 行 的高低值之和，我們這裡用到了一個幫助矩陣，它是原始矩陣從上到下加上去的。
假定原始矩陣是matrix, 它每層高低相加後獲得的矩陣是total，那末我們可以經由過程以下代碼完成：
int[][] total = matrix;
for (int i = 1; i < matrix[0].length; i++) {
for (int j = 0; j < matrix.length; j++) {
total[i][j] += total[i-1][j];
}
}
假如我們請求第 i 行到第 j 行之間高低值的和，我們可以經由過程total[j][k] - total[i-1][k] 獲得, k 的規模從1 到 matrix[0].length - 1。
有了這些常識點，我們只須要在一切的情形下，把它們所對應的部分最年夜子矩陣停止比擬，便可以獲得全局最年夜的子矩陣。代碼以下：
public int subMaxMatrix(int[][] matrix) {
int[][] total = matrix;
for (int i = 1; i < matrix[0].length; i++) {
for (int j = 0; j < matrix.length; j++) {
total[i][j] += total[i-1][j];
}
}
int maximum = Integer.MIN_VALUE;
for (int i = 0; i < matrix.length; i++) {
for (int j = i; j < matrix.length; j++) {
//result 保留的是從 i 行 到第 j 行 所對應的矩陣高低值的和
int[] result = new int[matrix[0].length];
for (int f = 0; f < matrix[0].length; f++) {
if (i == 0) {
result[f] = total[j][f];
} else {
result[f] = total[j][f] - total[i - 1][f];
}
}
int maximal = maxSubsequence(result);
if (maximal > maximum) {
maximum = maximal;
}
}
}
return maximum;
}
C說話相干的完成
標題
標題描寫：
已知矩陣的年夜小界說為矩陣中一切元素的和。給定一個矩陣，你的義務是找到最年夜的非空(年夜小至多是1 * 1)子矩陣。
好比，以下4 * 4的矩陣
0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
的最年夜子矩陣是
9 2 -4 1 -1 8
這個子矩陣的年夜小是15。
輸出：
輸出是一個N * N的矩陣。輸出的第一行給出N (0 < N <= 100)。
再前面的若干行中，順次（起首從左到右給出第一行的N個整數，再從左到右給出第二行的N個整數……）給出矩陣中的N2個整數，整數之間由空白字符分隔（空格或許空行）。
已知矩陣中整數的規模都在[-127, 127]。
輸入：
測試數據能夠有多組，關於每組測試數據，輸入最年夜子矩陣的年夜小。
樣例輸出：
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
樣例輸入：
15
AC代碼
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int i, j, h, k, n, max, sum, cur, matrix[101][101];
while (scanf("%d", &n) != EOF) {
// 初始化吸收矩陣
for (i = 0; i < n; i ++) {
for (j = 0; j < n; j ++)
scanf("%d", *(matrix + i) + j);
}
// 靜態計劃(相似於一維數組持續最年夜子序列和)
max = matrix[0][0];
for (i = 0; i < n; i ++) {
// i，j肯定高低界
for (j = i; j < n; j ++) {
// 初始化
for (k = i, sum = 0; k <= j; k ++)
sum += matrix[k][0];
if (sum > max)
max = sum;
for (h = 1; h < n; h ++) {
for (k = i, cur = 0; k <= j; k ++)
cur += matrix[k][h];
if (sum >= 0)
sum += cur;
else
sum = cur;
if (sum > max) max = sum;
}
}
}
printf("%d\n", max);
}
return 0;
}
