首页 > 代码库 > 矩形网格中寻找最长递增序列

矩形网格中寻找最长递增序列

在矩形网格中寻找最长的递增序列比如如下网格97,47,56,36
35,57,41,13
89,36,98,75
25,45,26,17结果要求输出17, 26, 36, 41, 47, 56, 57, 97基本想法就是对图中的每一个点都当作起始点试一编将序列最长的保存起来最后输出代码如下使用java编写import java.util.ArrayList;
public class 最长递增序列 {
	static int[][] rect={
			{97,47,56,36},
			{35,57,41,13},
			{89,36,98,75},
			{25,45,26,17}
	};
	static ArrayList<String> al=new ArrayList<String>();
	static ArrayList<String> longMax=new ArrayList<String>();
	public static void main(String[] args){
		
		for(int i=0;i<rect.length;i++)
			for(int j=0;j<rect[0].length;j++){
				seek(i,j);
				al=new ArrayList<String>();
			}
		System.out.println(longMax);
	}
	public static void seek(int bx,int by){
		al.add(rect[bx][by]+"");
		if(al.size()>longMax.size())
			longMax=new ArrayList(al);
		for(int x=-1;x<=1;x++)
			for(int y=-1;y<=1;y++)
				if(0<=bx+x && 0<=by+y && bx+x<=3 && by+y<=3 && rect[bx][by]<rect[bx+x][by+y]){
					seek(bx+x,by+y);
					al.remove(al.size()-1);
				}	
	}
}

矩形网格中寻找最长递增序列