POJ 1050 最大子段和的延伸最大子矩阵

野性酷女 2022-09-30 03:46 155阅读 0赞

1050计算最大子矩阵，枚举行（连续的），加到一个一维数组中，再利用一个一维数组求最大子矩阵的方法，得到临时的最大子段和，枚举结束之后，得到的就是整个矩阵的最大子段和了。

java code：

package test; import java.util.Scanner; //1050 public class Main \{ public static void main(String args\[\]) \{ Scanner cin = null; cin = new Scanner(System.in); int n = cin.nextInt(); int\[\]\[\] num = new int\[n\]\[n\]; for (int i = 0; i < n; i++) \{ for (int j = 0; j < n; j++) \{ num\[i\]\[j\] = cin.nextInt(); \} \} int\[\] sum = new int\[n\]; for (int i = 0; i < n; i++) \{ sum\[i\] = 0; \} int max = Integer.MIN\_VALUE;// 记录最大矩阵和 // 枚举连续的行，加到一起。从1开始枚举，一直到n for (int i = 1; i <= n; i++) \{ for (int j = 0; j < n&&(n - j) >= i; j++) \{// 从第一行开始枚举 // 一个二重循环计算几行之和 for (int m = 0; m < n; m++) \{ for (int k = j; k < i + j; k++) \{// k记录相加的当前行 sum\[m\] += num\[k\]\[m\]; \} \} // 得到sum之后，计算最大字段和 if (MaxSub(sum) > max)// 记住最大和 max = MaxSub(sum); // sum数组归0，下次重新使用 for (int t = 0; t < n; t++) \{ sum\[t\] = 0; \} \} \} System.out.println(max); \} public static int MaxSub(int\[\] arr) \{ int sum1; // tFirst,tSum为临时的最大子序列的第一个元素与和 int tSum; // 初始化 sum1 = tSum = arr\[0\]; // 遍历该数组 for (int i = 1; i < arr.length; i++) \{ // 如果tSum大于0，则将它与下一个元素相加，否则，arr\[i\]为子序列的第一个元素 if (tSum >= 0) tSum += arr\[i\]; else \{ tSum = arr\[i\]; \} // 如果临时的最大值大于实际的最大值，则更新子序列的first, last, sum if (sum1 < tSum) \{ sum1 = tSum; \} \} return sum1; \} \}