public class Main { static int[][] arr,sum; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt()+1, m = sc.nextInt()+1, k = sc.nextInt(); arr = new int[n][m]; sum = new int[n][m]; for (int i = 1; i < arr.length; i++) { String tmp = sc.next(); char[] tarr = tmp.toCharArray(); for (int j = 0; j < tarr.length; j++) { arr[i][j+1] = tarr[j]-'0'; } } int count = 0; for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { sum[i][j] = arr[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; } } for (int i = k; i < n; i++) { for (int j = k; j < m; j++) { int curr = sum[i][j]-sum[i-k][j]-sum[i][j-k]+sum[i-k][j-k]; if(curr > 0) count++; } } System.out.println(count); } }
时间: 2023-05-14 08:05:35 浏览: 65
这是一个 Java 程序,它的功能是计算一个二维数组中所有 k*k 的子矩阵中,元素和大于 0 的子矩阵的数量。具体实现方法是先计算出二维数组的前缀和,然后枚举所有 k*k 的子矩阵,计算它们的元素和,如果大于 0,则计数器加一。
相关问题
分析代码import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for(int i = 0;i < n;i++){ arr[i] = sc.nextInt(); } int sum = arr[0]; int max = arr[0]; //动态规划的方法 for(int i = 0;i < arr.length;i++){ sum = Math.max(sum + arr[i],arr[i]); max = Math.max(max,sum); } System.out.println(max); } }
这段代码实现了一个求最大子序和的算法,使用了动态规划的思想。具体分析如下:
1. 导入Java中的工具包java.util.*。
2. 定义了一个公共类Main。
3. 在main方法中,使用Scanner类从控制台读取一个整数n作为数组的长度,并且创建一个长度为n的整型数组arr。
4. 使用for循环遍历数组arr,依次将控制台输入的n个整数存储到数组arr中。
5. 定义了两个整型变量sum和max,分别表示当前最大子序和以及历史最大子序和,初始值都为数组的第一个元素arr[0]。
6. 使用for循环遍历数组arr,依次计算当前最大子序和和历史最大子序和。具体方法是:对于数组中的每一个元素arr[i],将其加到当前最大子序和sum上,然后和arr[i]取最大值,得到的结果再和历史最大子序和max取最大值,并将其赋值给max。
7. 输出历史最大子序和max。
通过这种动态规划的方式,可以在时间复杂度为O(n)的情况下,求出一个数组中的最大子序和。
解释代码public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int max=0; int sum=0; int[] arr = new int[n]; for(int i = 0;i < n;i++){ arr[i] = sc.nextInt(); sum = Math.max(sum + arr[i], arr[i]); max = Math.max(sum, max); } System.out.println(max); }
这段代码是一个求最大子段和的算法,其主要思路是使用动态规划。下面对代码进行解释:
1. 首先使用 Scanner 从控制台输入一个整数 n,表示接下来将输入 n 个整数。
2. 接下来定义一个长度为 n 的数组 arr,用于存储输入的 n 个整数。
3. 使用一个 for 循环,依次将 n 个整数存储到数组 arr 中。
4. 使用两个变量 max 和 sum 来记录最大子段和和当前子段和,初始值均为0。
5. 使用一个 for 循环,遍历数组 arr,对于每一个 arr[i],更新 sum:sum = Math.max(sum + arr[i], arr[i]),表示当前子段和为 sum + arr[i] 或者 arr[i] 中的最大值。
6. 在每次更新 sum 后,再更新 max:max = Math.max(sum, max),表示当前最大子段和为 sum 和 max 中的最大值。
7. 循环结束后,输出最大子段和 max。
这段代码的时间复杂度为O(n),是一种比较高效的求最大子段和的算法。