米拓企业网站管理系统,wordpress帐号,做设计一般在那个网站找图,网站 用户体验 考虑子数组最大累加和 给定一个数组arr,返回子数组的最大累加和
例:arr[1,-2,3,5,-2,6,-1];所有的子数组中[3,5,-2,6]可以累加出最大的和12#xff0c;所以返回12static void findByForce(int[] arr){int manSumarr[0];for(int i0;iarr.length;i){int sumarr[j];//某个元素为子…子数组最大累加和 给定一个数组arr,返回子数组的最大累加和
例:arr[1,-2,3,5,-2,6,-1];所有的子数组中[3,5,-2,6]可以累加出最大的和12所以返回12static void findByForce(int[] arr){int manSumarr[0];for(int i0;iarr.length;i){int sumarr[j];//某个元素为子数组的第一个元素int maxOfJsum;for(int ij;iarr.length;i){sumarr[i];//累加后续元素if(summaxOfJ){maxOfJsum;//某个元素后续最大累加}}if(maxOfJmaxSum){maxSummaxOfJ;// 总的最大值}}System.out.println(maxSum);
}//递推法 o(n)
static int findByDp(int[] arr){int sumJarr[0];///前J个元素的最大贡献int maxsumJ;int left0right0;//***若是求最大值之间的下标int temp;//记录最大值的letffor(int j1;jarr.length;j){if(sumJ0){//左子表的最大和为正继续向后累加sumJarr[j];//若是大于0则可以要前面的一段}else{//若是小于0则从当前位置重新开始sumJarr[j];// leftj;//重新开始时更新left//**上面那行是错的他最终只会停在最后一次sumJ小于0的位置tempj;}if(sumJmax){//最大值lefttemp;//*如此只有最大值得到更新才能更新letfmaxsumJ;// 每次求得最大值更新最大值时同时更新rightrightj;}}return max;} 子矩阵最大累加和 给定一个矩阵matrix,其中的值有正、有负、有0、返回子矩阵的最大累加和
例如matrix为:
-1 -1 -1
-1 2 2
-1 -1 -1
其中最大累加和的子矩阵为
2 2
所以返回4从第一行开始作为起始行先求第一行找最大子数组和再将下一行于上一行累加到一起找最大子数组和然后变更起始行继续之前的循环private static int maxSum(int[][] matrix){int beginRow0;final int Mmatrix.length;final int Nmatrix[0].length;int[] sumsnew int[N];//按列求和int max0;//历史最大的子矩阵和while(beginRowM){//起始行for(int ibeginRow;iM;i){//从起始行到最后一行//按列累加for(int j0;jN;j){sums[j]matrix[i][j];}//累加完成int tfindByDp(sums);//求出sums的最大和子数组if(tmax)maxt;}//另起一行作为起始行把sums清零Arrays.fill(sums,0);//将sums的每个元素都设定为0beginRoww;//以下一行作为起始行}return max;}public static int findByDp(int[] arr){if(arr.length0)return 0;int sumJarr[0];///前J个元素的最大贡献int maxsumJ;int left0right0;//***若是求最大值之间的下标int temp;//记录最大值的letffor(int j1;jarr.length;j){if(sumJ0){//左子表的最大和为正继续向后累加sumJarr[j];//若是大于0则可以要前面的一段}else{//若是小于0则从当前位置重新开始sumJarr[j];// leftj;//重新开始时更新left//**上面那行是错的他最终只会停在最后一次sumJ小于0的位置tempj;}if(sumJmax){//最大值lefttemp;//*如此只有最大值得到更新才能更新letfmaxsumJ;// 每次求得最大值更新最大值时同时更新rightrightj;}}return max;}
