import java.util.*;
public class Test {    
    static class DataNode { //定义一个类用于记录数组元素的位置的值
        int x, y, value;
        public DataNode(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }

    static class DataList implements Comparable<DataList> { //定义一个类用于记录路径
        int sum = 0;
        List<DataNode> nodes = new ArrayList<DataNode>();

        public DataList() {}
        public void addNode(DataNode node) {
            nodes.add(0, node);
            sum += node.value;
        }
        public int compareTo(DataList dl) {
            return dl.sum - sum;
        }
    }

    public static void main(String[] args) throws Throwable {
        int[][] number={
            {22,32,14,77,45},
            {0,12,34,37,23},
            {0,0,44,23,15},
            {0,0,0,34,54},
            {0,0,0,0,88}};

        List<DataList> result = findAll(number, 0, 0); //获取所有路径
        if (result.size() > 0) {
            Collections.sort(result); //降序排序所有路径
            //for (DataList dl : result) {
            DataList dl = result.get(0); //取出第一条路径（该路径权值最大）
                System.out.printf("sum=%d\n", dl.sum);
                for (DataNode n : dl.nodes) {
                    System.out.printf("(%d,%d:%d), ", n.x, n.y, n.value);
                }
                System.out.println();
            //}
        }
    }

    //定义一个递归寻找所有路径的方法
    public static List<DataList> findAll(int[][] number, int x, int y) {
        if (number==null || number.length==0 || number[0].length==0) {
            return new ArrayList<DataList>(); //非法数据的时候返回0元素的集合
        }

        List<DataList> result = new ArrayList<DataList>();
        if (x==number.length-1 && y==number[0].length-1) { //路径走到终点的时候递归结束
            DataList dl = new DataList();
            dl.addNode(new DataNode(x, y, number[x][y]));
            result.add(dl);
            return result;
        }

        if (x < number.length && y < number[0].length) { //右下有效时递归取右下路径集合
            List<DataList> tmp = findAll(number, x+1, y+1);
            for (DataList dl : tmp) { //在递归获取的子集合中追加当前元素
                dl.addNode(new DataNode(x, y, number[x][y])); 
            }
            result.addAll(tmp); //把右下方的子集合路径追加到最终的结果集中
        }
        if (y < number[0].length) { //右方有效时递归取右方路径集合
            List<DataList> tmp = findAll(number, x, y+1);
            for (DataList dl : tmp) { //同上
                dl.addNode(new DataNode(x, y, number[x][y]));
            }
            result.addAll(tmp);
        }
        if (x < number.length) { //下方有效时递归取下方有效集合
            List<DataList> tmp = findAll(number, x+1, y);
            for (DataList dl : tmp) { //同上
                dl.addNode(new DataNode(x, y, number[x][y]));
            }
            result.addAll(tmp);
        }
        return result;
    }
}

------解决方案--------------------
数可以为负数没