import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;

//33333333333333
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N=in.nextInt();
        a=new int[N];
        for (int i = 0; i < N; i++) {
            a[i]=in.nextInt();
        }
        new Main().dfs(0);
    }
    static int[] a;
    static int N;
    static HashSet<Integer> set=new HashSet<>();//记录是否访问过
    public void dfs(int i){
        if(i>=N) return;

        System.out.print(a[i]+" ");
        set.add(i);
        int l=2*i+1;//左子节点
        int r=2*i+2;//右子节点
        int r_bro=i+1;//右兄弟
        int fa=(i-1)/2;//父亲节点
        //以下按照左子 右子 右兄弟 父亲的顺序进行dfs
        if(0<=l&&l<N&&!set.contains(l)){
            dfs(l);
        }
        else if(0<=r&&r<N&&!set.contains(r)){
            dfs(r);
        }
        else if(0<=r_bro&&r_bro<N&&!set.contains(r_bro)){
            dfs(r_bro);
        }
        else {//这里注意区分当前节点的父节点是不是最靠右的节点
            //先判断父节点的右边节点有没有被访问（排序父亲节点是内部节点的情况）
            if(!set.contains(fa+1)) dfs(fa+1);
            else if(!set.contains(fa)) dfs(fa);
            else return;
        }
    }
}

输入输出：

说明：第一行：行数 列数

            以下：矩阵值

输出：11，因为第一列与第三列首尾相连且最大，所以为1+3+2+5=11

思想：参照leecode面试题14：最大子矩阵。

本题特殊处理：将输入的矩阵反转，并且将第一行复制到最后一行，枚举长度时注意控制子矩阵的长度

import java.io.*;
import java.util.*;
/*
思想：将所有子矩阵的和求出，取最大。这个过程要转为一维的求最大连续子数组。
*/
public class Main {

    public static void main(String[] args) throws IOException {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt(),m=in.nextInt();
        int[][] a=new int[m+1][n];//要点，将原矩阵逆时针转90度，然后将第一行复制到最后一行，来解决首尾链接的情况
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[j][i]=in.nextInt();
            }
        }
        for (int i = 0; i <n; i++) {
            a[m][i]=a[0][i];//将第一行复制变为最后一行
        }
        System.out.println(new Main().getMaxMatrix(a));

    }
    public int getMaxMatrix(int[][] matrix) {
            int x=matrix.length;
            int y=matrix[0].length;
            int[][] a=new int[x][y];
        int mmax=Integer.MIN_VALUE;//记录最大值
        //以下开始枚举子矩阵
        for(int i=0;i<x;i++){//枚举起点
            int[] b=new int[y];//因为是从上开始逐级向下扩展，所以不必重复计算和，只要在上次长度拓展的基础上+就可以了
            for(int j=i,t=0;j<x&&t<x-1;j++,t++){//枚举终点：要点：用t来控制子矩阵的上下长度不超过原来矩阵的长度
                int sum=Integer.MIN_VALUE;
                for(int k=0;k<y;k++){
                    b[k]+=matrix[j][k];
                    if(sum<=0){
                        sum=b[k];
                    }
                    else{
                        sum=b[k]+sum;
                    }
                    if(sum>mmax){
                        mmax=sum;
                    }
                }
            }
        }
        return mmax;

    }

}