Luogu:P1719

LLLgoyour · Jun 16, 2023 · 0ea89a9 · 0ea89a9
1 parent 4c583c3
commit 0ea89a9
Showing 1 changed file with 35 additions and 28 deletions.
diff --git a/luogu/P1719/Main.java b/luogu/P1719/Main.java
@@ -1,46  1,53 @@
-import java.io.*;
 import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 
 public class Main {
-    public static int[][] prefixSums(int[][] in) {
-        int[][] preSum = new int[in.length][in[0].length];
-        preSum[0][0] = in[0][0];
-
-        // prefix sum of first column and first row
-        for (int i = 1; i < in.length; i  ) {
-            preSum[i][0] = preSum[i - 1][0]   in[i][0];
-            preSum[0][i] = preSum[0][i - 1]   in[0][i];
     public static int maxSubArray(int[] arr) {
         int maxSum = arr[0];
         int currentSum = arr[0];
 
         for (int i = 1; i < arr.length; i  ) {
             currentSum = Math.max(arr[i], currentSum   arr[i]);
             maxSum = Math.max(maxSum, currentSum);
         }
 
-        // prefix sum in general
-        for (int i = 1; i < in.length; i  ) {
-            for (int j = 1; j < in[0].length; j  ) {
-                preSum[i][j] = preSum[i - 1][j]   preSum[i][j - 1] - preSum[i - 1][j - 1]   in[i][j];
         return maxSum;
     }
 
     public static int maxWeightedRectangleSum(int[][] matrix) {
         int n = matrix.length;
         int maxSum = Integer.MIN_VALUE;
 
         for (int left = 0; left < n; left  ) {
             int[] rowSum = new int[n];
 
             for (int right = left; right < n; right  ) {
                 for (int i = 0; i < n; i  ) {
                     rowSum[i]  = matrix[i][right];
                 }
 
                 int currentSum = maxSubArray(rowSum);
                 maxSum = Math.max(maxSum, currentSum);
             }
         }
 
-        return preSum;
         return maxSum;
     }
 
     public static void main(String[] args) throws IOException {
         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
         int n = Integer.parseInt(in.readLine());
-        int[][] arr = new int[n][n];
         int[][] matrix = new int[n][n];
         for (int i = 0; i < n; i  ) {
-            String[] s = in.readLine().split(" ");
             String[] row = in.readLine().split(" ");
             for (int j = 0; j < n; j  ) {
-                arr[i][j] = Integer.parseInt(s[j]);
                 matrix[i][j] = Integer.parseInt(row[j]);
             }
         }
         in.close();
-        int[][] preSum = prefixSums(arr);
-        int max = 0;
-        for (int i = 0; i < n; i  ) {
-            for (int j = 0; j < n; j  ) {
-                if (preSum[i][j] > max) {
-                    max = preSum[i][j];
-                }
-            }
-        }
-        System.out.println(max);
 
         int maxSum = maxWeightedRectangleSum(matrix);
         System.out.println(maxSum);
     }
-}
 }