首页 > 代码库 > 求一维数组中不重叠的两个子数组的最大和
求一维数组中不重叠的两个子数组的最大和
给定一个长度为N的整数数组a，求不重叠的两个子数组的和的最大值。
如a[6]={1, 2, -4, 3, 2, -5}。所取的子数组分别为{1，2}{3, 2}时，两个子数组的和最大，为3+5=8。
这个题目是数组的子数组最大和（即最大连续和）的变形（后面附上了求解子数组最大和的程序）。
一种方法是把数组分成两部分（[0~i]和[i+1~len-1]），分别求两部分的最大连续和相加，再从中选出最大的。时间复杂度是O(N*N)。这种方法在求解最大连续和时会有冗余的计算，需要优化。
第二种方法申请两个独立数组，用sum1[i]记录数组[0~i]的最大连续和，sum2[i]记录数组[i, len-1]的最大连续和。那么max(sum1[i]+sum2[i+1]) for every 0<=i<len-1 就是所求的最大值。时间复杂度O(N)。代码如下：
bool max2Sum(int* arr, int len, int& max){ if (arr == NULL || len <= 1) return false; // sum1[i]，从0到i的最大连续和 int sum1[len]; // sum2[i]，从i到len-1的最大连续和 int sum2[len]; int sum = arr[0]; sum1[0] = sum; for (int i = 1; i < len - 1; i++) { if (sum <= 0) sum = arr[i]; else sum += arr[i]; if (sum1[i-1] < sum) sum1[i] = sum; else sum1[i] = sum1[i-1]; } sum = arr[len-1]; sum2[len-1] = sum; for (int i = len - 2; i > 0; i--) { if (sum <= 0) sum = arr[i]; else sum += arr[i]; if (sum2[i+1] < sum) sum2[i] = sum; else sum2[i] = sum2[i+1]; } int max = sum1[0] + sum2[1]; for (int i = 1; i < len - 1; i++) { if (max < sum1[i] + sum2[i+1]) max = sum1[i] + sum2[i+1]; } return max;}
求解单个子数组和最大值的代码如下：
bool maxSum(int* arr, int len, int& max){ if (arr == NULL || len <= 0) return false; int sum = arr[0]; int max = sum; for (int i = 1; i < len; i++) { if (sum <= 0) sum = arr[i]; else sum += arr[i]; if (sum > max) max = sum; } return true;}
求一维数组中不重叠的两个子数组的最大和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。