【蓝桥杯】历届试题最大子阵（运行超时）

历届试题最大子阵

时间限制：1.0s 内存限制：256.0MB

问题描述

　　给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。

　　其中，A的子矩阵指在A中行和列均连续的一块。

输入格式

　　输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。
　　接下来n行，每行m个整数，表示矩阵A。

输出格式

　　输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。

样例输入

3 3
-1 -4 3
3 4 -1
-5 -2 8

样例输出

样例说明

　　取最后一列，和为10。

数据规模和约定

　　对于50%的数据，1<=n, m<=50；
　　对于100%的数据，1<=n, m<=500，A中每个元素的绝对值不超过5000。

以下是超时代码：

Java源代码：

 1 import java.util.Scanner;
 2 
 3 public class Main {
 4 
 5     static int INF = 0x3f3f3f3f;
 6     static int MAXN = 550;
 7     static int[][] mp = new int[MAXN][MAXN];
 8     static int[] dp = new int[MAXN];
 9     static int mx;
10     static int m, n;
11 
12     static void solve(int[] a) {
13         int temp = 0;
14         for (int j = 0; j < n; j++) {
15             if (temp + a[j] < a[j])
16                 temp = a[j];
17             else
18                 temp += a[j];
19             mx = Math.max(mx, temp);
20         }
21     }
22 
23     public static void main(String[] args) {
24         Scanner sc = new Scanner(System.in);
25         m = sc.nextInt();
26         n = sc.nextInt();
27         mx = -INF;
28         for (int i = 0; i < m; i++)
29             for (int j = 0; j < n; j++)
30                 mp[i][j] = sc.nextInt();
31         for (int i = 0; i < m; i++) {
32             for (int j = 0; j < dp.length; j++) {
33                 dp[j] = 0;
34             }
35             for (int j = i; j < m; j++) {
36                 for (int k = 0; k < n; k++)
37                     dp[k] += mp[j][k];
38                 solve(dp);
39             }
40         }
41         System.out.println(mx);
42     }
43 }

评测点序号	评测结果	得分	CPU使用	内存使用	下载评测数据
1	正确	10.00	156ms	24.62MB	输入输出
2	正确	10.00	234ms	25.00MB	输入输出
3	正确	10.00	296ms	29.43MB	输入输出
4	正确	10.00	234ms	32.38MB	输入输出
5	正确	10.00	343ms	34.98MB	输入输出
6	运行超时	0.00	运行超时	87.85MB	输入输出
7	运行超时	0.00	运行超时	98.69MB	输入输出
8	运行超时	0.00	运行超时	115.7MB	输入输出
9	运行超时	0.00	运行超时	87.36MB	输入输出
10	运行超时	0.00	运行超时	124.4MB	输入输出

【蓝桥杯】历届试题 最大子阵（运行超时）

【蓝桥杯】历届试题最大子阵（运行超时）