题目:返回一个二维整数数组中最大联通子数组的和。
要求：
1.1输入一个二维整形数组；
1.2数组里有正数也有负数；
1.3要求时间复杂度为O(n)。
设计思路：
2.1：建立一个2维数组shuzu[][]，第一列用于存放数组元素，第二列用于表示本字符以前的最大子数组和的值
2.2：输入数组，并把数组放在第一列,如输入1，2，3……，shuzu[1][z],shuzu[2][z],shuzu[3][z]
2.3：
| 下标 | 0 | 1 | 2 | 3 | 4 |
| Shuzu[shu][0] | -1 | 3 | 4 | -4 | 1 |
| Shuzu[shu]1] | -1 | 3 | 7 | 7 | 8 |
Shuzu[shu][0]存放输入的数组，
Shuzu[shu][1]存放输入的数组，
2.4：输入的数组是放在Shuzu[shu][0]，初始化Shuzu[shu][1]=Shuzu[0][0]
2.5：子数组交换：Shuzu[shu-1][0]
huzu[0][1]=shuzu[0][0]; for(int i = 1;i < shu;i++) { if(shuzu[i-1][1]<0) { shuzu[i][1]=shuzu[i][0]; } if(shuzu[i-1][1]>=0) { shuzu[i][1] = shuzu[i-1][1]+shuzu[i][0]; } } int max=shuzu[0][1]; for(int i=1;i<shu;i++) { if(shuzu[i][1]>=max) { max=shuzu[i][1]; } }
2.6；输出最大值：
实验代码：
package shuzu; import java.util.Scanner; public class DongTai01 { public static void main(String args[]) { Scanner num = new Scanner(System.in); System.out.println("请输入数组的长度"); int a = num.nextInt(); int shu = a; int[][] shuzu = new int[shu][2]; Scanner sca = new Scanner(System.in); System.out.println("请输入" + shu + "以内个整数"); for(int i = 0;i < shu;i++) { shuzu[i][0] = sca.nextInt(); System.out.println("你已经输入" + (i +1) + "个数" + "，还有"+(shu -i -1)+"个数"); if(i == shu-1) { break; } } for(int z = 0;z <shu;z++) { System.out.println(shuzu[z][0] ); } shuzu[0][1]=shuzu[0][0]; for(int i = 1;i < shu;i++) { if(shuzu[i-1][1]<0) { shuzu[i][1]=shuzu[i][0]; } if(shuzu[i-1][1]>=0) { shuzu[i][1] = shuzu[i-1][1]+shuzu[i][0]; } } int max=shuzu[0][1]; for(int i=1;i<shu;i++) { if(shuzu[i][1]>=max) { max=shuzu[i][1]; } } System.out.println("最大和为"+max); } }
实验截图：
4.1全正数：
4.2全负数：
4.3.有正有负：
