Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Java解决方案

Posted by tiezhu at 2022-03-10 17:09:46 on Problem 1050
import java.util.Scanner;

/**
 * @author Wanghs
 * @create 2022/3/10
 * @description
 */
public class Main{
    private static int[][] sum; //s(i,j)代表以第i行第j个元素为起始,垂直长度为row+1的列的和。
    private static int[][] arr; //存储二维数组

    private static int n; //存储二维数组的边长
    private static int totalMax = -12800; //存储最终结果


    private static void findMax() {

        int[] rowP = new int[n]; //动态规划序列
        int[] rowA = new int[n]; //放置当前操作行

        for (int row = 0; row < n; row++) {
            for (int i = 0; i < (n - row); i++) {
                rowA = arr[row + i];
                for (int j = 0; j < n; j++) {
                    sum[row][j] += rowA[j];
                }

                rowP[0] = sum[row][0];   //问题转化成,在这个行中,求最大字段和的问题

                for (int j = 1; j < n; j++) {    //一维最大子序列和的问题
                    if (rowP[j - 1] < 0) {
                        rowP[j] = sum[row][j];
                    } else {
                        rowP[j] = rowP[j - 1] + sum[row][j];
                    }
                }

                int max = -12800;
                for (int j = 0; j < n; j++) {
                    if (rowP[j] > max) {
                        max = rowP[j]; //求出的max就是在垂直长度为row+1的所有矩形中,矩形内元素和的最大值
                    }
                }
                if (totalMax < max) {
                    totalMax = max; //最终结果
                }
            }
        }
    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n][n];
        sum = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scan.nextInt();
            }
        }
        findMax();
        System.out.println(totalMax);
        scan.close();
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator