做网站的流程分析,网站建设申请总结,软件开发去哪里学,网站推广公司官网题目:返回一个二维整数数组中最大联通子数组的和。 要求#xff1a; 输入一个二维整形数组#xff0c;数组里有正数也有负数。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 开发方式#xff1a;团队开发 主要思路#xff1a;二维连通数组求最大子数组#xff0c;我…题目:返回一个二维整数数组中最大联通子数组的和。 要求 输入一个二维整形数组数组里有正数也有负数。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 开发方式团队开发 主要思路二维连通数组求最大子数组我们在这里主要运用了降维的思想主要是通过将二维数组转化为一维数组求最大子数组的思想在项目中定义一个算法用于实现一行连续数组的最大子数组并用p q记录最大子数组的起始结束位置下标。在主函数中利用for循环实现二维数组每一行最大子数组的求和在利用循环实现最大子数组的连接添加对单独正数据的判断从而实现连通的最大子数组问题。 代码如下 import java.util.Scanner;public class Test
{static int q0,p0;static Scanner strnew Scanner(System.in);public static void main(String args[]){int m10,m20; int max0;int sum0;System.out.println(输入二维数组的行列数);m1str.nextInt();m2str.nextInt();int [][]anew int[m1][m2];int []bnew int[m2];int []leftnew int[m2];int []rightnew int[m2];int []tnew 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; im1; i)//求每一行最大子数组{for (int j 0; jm2; 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 1m2; i)//将最大子数组合并{if (left[i] right[i 1] right[i] left[i 1])//两行的最大子数组块相连{max t[i 1];}for (int j left[i]; jleft[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 []bnew int[a.length1]; b[a.length]0;int sum10;int max10;for(int i0;in;i){if(sum10){sum1a[i];}else{sum1sum1a[i];}b[i] sum1;}max1b[0];for(int i0;in;i){if(max1b[i]){max1b[i];qi;}}for(int iq;i0;i--){if(b[i]a[i]){pi;break;}}return max1;}
} 转载于:https://www.cnblogs.com/yuezhihao/p/6679699.html
