·主要思路:二维连通数组求最大子数组,我们在这里主要运用了降维的思想,主要是通过将二维数组转化为一维数组求最大子数组的思想,在项目中定义一个算法,用于实现一行连续数组的最大子数组,并用p q记录最大子数组的起始结束位置下标。在主函数中利用for循环实现二维数组每一行最大子数组的求和,在利用循环实现最大子数组的连接,添加对单独正数据的判断,从而实现连通的最大子数组问题。
·代码如下
import java.util.Scanner; public class Test { static int q=0,p=0; static Scanner str=new Scanner(System.in); public static void main(String args[]) { int m1=0,m2=0; int max=0; int sum=0; System.out.println("输入二维数组的行列数"); m1=str.nextInt(); m2=str.nextInt(); int [][]a=new int[m1][m2]; int []b=new int[m2]; int []left=new int[m2]; int []right=new int[m2]; int []t=new int[m2]; for (int i = 0; i < m1; i++) { for (int j = 0; j < m2; j++) { a[i][j]=str.nextInt(); } } for (int i = 0; i<m1; i++)//求每一行最大子数组 { for (int j = 0; j<m2; j++) { b[j] = a[i][j]; } sum = findmax(m1, b, p, q); left[i] = p; //记录最大子数组的坐标位置 right[i] = q; t[i] = sum; } max = t[0]; for (int i = 0; i + 1<m2; i++)//将最大子数组合并 { if (left[i] <= right[i + 1] && right[i] >= left[i + 1])//两行的最大子数组块相连 { max += t[i + 1]; } for (int j = left[i]; j<left[i + 1]; j++) { if (a[i + 1][j]>0) max += a[i + 1][j]; //判别独立正数 } } System.out.println("最大子数组和为:"+max); } public static int findmax(int n,int a[],int p, int q ) { int []b=new int[a.length+1]; b[a.length]=0; int sum1=0; int max1=0; for(int i=0;i<n;i++) { if(sum1<0) { sum1=a[i]; } else { sum1=sum1+a[i]; } b[i] = sum1; } max1=b[0]; for(int i=0;i<n;i++) { if(max1<b[i]) { max1=b[i]; q=i; } } for(int i=q;i>=0;i--) { if(b[i]==a[i]) { p=i; break; } } return max1; } }
·结果截图: