【作业】返回一个整形数组中最大子数组地和——当维度达到二维/*待完善*/

//没有写完，只写完了我自己定义的针对块的各种运算方法。

我将每一个矩形看作一个块，通过点连成行，行连成块的思路进行各种操作。

（1）算出每一个正数块

（2）将块排序

（3）将1号（第一大的）和2号（第二大的，以此类推）相加，看是否使得新块比旧块大，是则合并成新的块否则比较1号和3号……

（4）……

（5）只剩下一个不能再大的块即为最终结果

思路可能有缺陷，待更改

点、行、块

 1 package geren_04;
 2 
 3 class D//点
 4 {
 5     private int num;
 6     private int x;
 7     private int y;
 8     public D(){};
 9     public D(int num,int x,int y)
10     {
11         this.num=num;
12         this.x=x;
13         this.y=y;
14     }
15     public D(int x,int y)
16     {
17         this.x=x;
18         this.y=y;
19     }
20     public int getX() {
21         return x;
22     }
23     public void setX(int x) {
24         this.x = x;
25     }
26     public int getY() {
27         return y;
28     }
29     public void setY(int y) {
30         this.y = y;
31     }
32     public int getNum() {
33         return num;
34     }
35     public void setNum(int num) {
36         this.num = num;
37     }
38     public void show()
39     {
40         System.out.println("("+x+" , "+y+" ) : "+num);
41     }
42 }
D
 1 package geren_04;
 2 
 3 import java.util.ArrayList;
 4 
 5 public class H //行
 6 {
 7     private int sum;
 8     private D Z;
 9     private D Y;
10     private ArrayList<D> h;
11     public H() {}
12     public H(D Z,D Y) 
13     {
14         this.Z=Z;
15         this.Y=Y;
16     }
17     public String toString()
18     {
19         String s="";
20         s+="# 
( "+Z.getX()+" , "+Z.getY()+" ) to ( "+Y.getX()+" , "+Y.getY()+" )";
21         for(int i=0;i<h.size();i++)
22         {
23             s+=h.get(i)+" ";
24         }
25         s+="#
";
26         
27         return s;
28     }
29     public void setValue(ArrayList<D> h)
30     {
31         this.h=h;
32     }
33     public int getSum()
34     {
35         D d=new D();
36         sum=0;
37         for(int i=0;i<h.size();i++)
38         {
39             d=h.get(i);
40             sum+=d.getNum();
41         }
42         return sum;
43     }
44     public int getD(int i)
45     {
46         return h.get(i).getNum();
47     }
48     public void show()
49     {
50         System.out.println("# 
( "+Z.getX()+" , "+Z.getY()+" ) to ( "+Y.getX()+" , "+Y.getY()+" )");
51         for(int i=0;i<h.size();i++)
52         {
53             System.out.print(h.get(i).getNum()+" ");
54         }
55         System.out.println("
#
");
56     }
57     public D getZ() {
58         return Z;
59     }
60     public void setZ(D z) {
61         Z = z;
62     }
63     public D getY() {
64         return Y;
65     }
66     public void setY(D y) {
67         Y = y;
68     }
69     public void setSum(int sum) {
70         this.sum = sum;
71     }
72     
73 }
H
  1 package geren_04;
  2 
  3 import java.util.ArrayList;
  4 class K//块
  5 {
  6     private int flag;
  7     //左上顶点
  8     private D ZS;
  9     //右上顶点
 10     private D YS;
 11     //左下顶点
 12     private D ZX;
 13     //右下顶点
 14     private D YX;
 15     private int l;//长-横着
 16     private int w;//宽-竖着
 17     private int sum;
 18     private ArrayList<H> k=new  ArrayList<H>();
 19     public K() {l=0;w=0;}
 20     public K(D ZS,D YS, D ZX, D YX) 
 21     {
 22         this.ZS=ZS;
 23         this.YS=YS;
 24         this.ZX=ZX;
 25         this.YX=YX;
 26         this.l=YS.getX()-ZS.getX();
 27         this.w=ZX.getY()-ZS.getY();
 28     }
 29     public void setValue(ArrayList<H> k)
 30     {
 31         this.k=k;
 32     }
 33     public int getSum()
 34     {
 35         sum=0;
 36         for(int i=0;i<w;i++)
 37         {
 38             sum+=k.get(i).getSum();
 39         }
 40         return sum;
 41     }
 42     public void show()
 43     {
 44         H h=new H();
 45         System.out.println("#
( "+ZS.getX()+" , "+ZS.getY()+" ) to ( "+YS.getX()+" , "+YS.getY()+" )");
 46         System.out.println("( "+ZX.getX()+" , "+ZX.getY()+" ) to ( "+YX.getX()+" , "+YX.getY()+" )");
 47         for(int i=0;i<w;i++)
 48         {
 49             for(int t=0;t<l;t++)
 50             {
 51                 System.out.print(k.get(i).getD(t)+"	");
 52             }
 53             System.out.println("");
 54         }
 55         System.out.println("#
");
 56     }
 57     
 58     public D getD(int x,int y)
 59     {
 60         D d=new D();
 61         d.setX(x);
 62         d.setY(y);
 63         d.setNum(k.get(y).getD(x));
 64         return d;
 65     }
 66     public D getZS() {
 67         return ZS;
 68     }
 69     public void setZS(D zS) {
 70         ZS = zS;
 71     }
 72     public D getYS() {
 73         return YS;
 74     }
 75     public void setYS(D yS) {
 76         YS = yS;
 77     }
 78     public D getZX() {
 79         return ZX;
 80     }
 81     public void setZX(D zX) {
 82         ZX = zX;
 83     }
 84     public D getYX() {
 85         return YX;
 86     }
 87     public void setYX(D yX) {
 88         YX = yX;
 89     }
 90     public int getL() {
 91         return l;
 92     }
 93     public void setL(int l) {
 94         this.l = l;
 95     }
 96     public int getW() {
 97         return w;
 98     }
 99     public void setW(int w) {
100         this.w = w;
101     }
102     public int getFlag() {
103         return flag;
104     }
105     public void setFlag(int flag) {
106         this.flag = flag;
107     }
108     
109     
110     
111 }
K

工具类

  1 package geren_04;
  2 
  3 import java.util.ArrayList;
  4 
  5 public class KUtil 
  6 {
  7     public static int max(int... a)//最大
  8     {
  9         int max=a[0];
 10         for(int i:a)
 11         {
 12             if(max<=i)
 13             {
 14                 max=i;
 15             }
 16         }
 17         return max;
 18     }
 19     public static int min(int... a)//最小
 20     {
 21         int min=a[0];
 22         for(int i:a)
 23         {
 24             if(min>=i)
 25             {
 26                 min=i;
 27             }
 28         }
 29         return min;
 30     }
 31     public static K KCreateAll(int w,int l,int[][] list)//初始化最大的块  k all，有bug刚改，所有怀疑下面几个也有bug
 32     {
 33         D zs=new D(0,0);
 34         D ys=new D(l,0);
 35         D zx=new D(0,w);
 36         D yx=new D(l,w);
 37         K k=new K(zs,ys,zx,yx);
 38         ArrayList<H> kList=new ArrayList<H>();
 39         ArrayList<D> hList=new ArrayList<D>();
 40         H h=new H();
 41         D d=new D();
 42         D z=new D();
 43         D y=new D();
 44         
 45         
 46         for(int i=0;i<w;i++)
 47         {
 48             hList=new ArrayList<D>();
 49             h=new H();
 50             z=new D();
 51             y=new D();
 52             
 53             z.setX(0);
 54             y.setX(l);
 55             z.setY(i);
 56             y.setY(i);
 57             for(int t=0;t<l;t++)
 58             {
 59                 d=new D();
 60                 d.setX(t);
 61                 d.setY(i);
 62                 d.setNum(list[i][t]);
 63                 hList.add(d);
 64                 //hList.get(hList.size()-1).show();
 65             }
 66             
 67             h.setZ(z);
 68             h.setY(y);
 69             h.setValue(hList);
 70             h.getSum();
 71             kList.add(h);
 72             kList.get(0).show();
 73         }
 74         k.setValue(kList);
 75         k.getSum();
 76         return k;
 77     }
 78     public static ArrayList<K> KCreate(int w,int l,int[][] list)//创建块，怀疑有bug
 79     {
 80         ArrayList<K> EKList=new ArrayList<K>();
 81         K k;
 82         D d=new D();
 83         H h;
 84         ArrayList<H> kList=new ArrayList<H>();
 85         ArrayList<D> hList=new ArrayList<D>();
 86         //创建块
 87         for(int i=0;i<w;i++)
 88         {
 89             for(int t=0;t<l;t++)
 90             {
 91                 kList.clear();
 92                 hList.clear();
 93                 d.setX(t);
 94                 d.setY(i);
 95                 d.setNum(list[i][t]);
 96                 k=new K(d,d,d,d);
 97                 h=new H(d,d);
 98                 hList.add(d);
 99                 h.setValue(hList);
100                 kList.add(h);
101                 k.setValue(kList);
102                 k.getSum();
103             }
104         }
105         return EKList;
106     }
107     public static K KAdd(K k1,K k2,K all)//块的加法，怀疑有bug
108     {
109         D zs=new D();
110         D ys=new D();
111         D zx=new D();
112         D yx=new D();
113         D d1=new D();
114         D d2=new D();
115         //确定四个角
116         //左上的点
117         d1=k1.getZS();
118         d2=k2.getZS();
119         //x
120         zs.setX(min(d1.getX(),d2.getX()));//取最小
121         //y
122         zs.setY(min(d1.getY(),d2.getY()));//取最小
123         //右上的点
124         d1=k1.getYS();
125         d2=k2.getYS();
126         //x
127         ys.setX(min(d1.getX(),d2.getX()));//取最小
128         //y
129         ys.setY(min(d1.getY(),d2.getY()));//取最小
130         //左下的点
131         d1=k1.getZX();
132         d2=k2.getZX();
133         //x
134         zx.setX(min(d1.getX(),d2.getX()));//取最小
135         //y
136         zx.setY(min(d1.getY(),d2.getY()));//取最小
137         //右下的点
138         d1=k1.getYX();
139         d2=k2.getYX();
140         //x
141         yx.setX(min(d1.getX(),d2.getX()));//取最小
142         //y
143         yx.setY(min(d1.getY(),d2.getY()));//取最小
144         //
145         K k=new K(zs,ys,zx,yx);
146         /*赋值*/
147         //获得LIST
148         ArrayList<H> kList=new ArrayList<H>();
149         ArrayList<D> hList=new ArrayList<D>();
150         H h=new H();
151         D d=new D();
152         D z=new D();
153         D y=new D();
154         z.setX(zs.getX());
155         y.setX(ys.getX());
156         for(int i=0;i<k.getW();i++)
157         {
158             hList.clear();
159             z.setY(zs.getY()+i);
160             for(int t=0;t<k.getL();t++)
161             {
162                 d=all.getD(t, i);
163                 hList.add(d);
164             }
165             h.setZ(z);
166             h.setY(y);
167             h.setValue(hList);
168             h.getSum();
169             kList.add(h);
170         }
171         k.setValue(kList);
172         k.getSum();
173         return k;
174     }
175     
176 }
KUtil
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/CCRNRT/p/10590678.html