首页 > 代码库 > 最大子数组和(最大子段和)
最大子数组和(最大子段和)
比如对于数组[1,-2,3,5,-1,2] 最大子数组和是sum[3,5,-1,2] = 9, 我们要求函数输出子数组和的最大值,并且返回子数组的左右边界(下面函数的left和right参数).
本文我们规定当数组中所有数都小于0时,返回数组中最大的数(也可以规定返回0,只要让以下代码中maxsum初始化为0即可,此时我们要注意-1 0 0 0 -2这种情形,特别是如果要求输出子数组的起始位置时,如果是面试就要和面试官问清楚)
以下代码我们在PAT 1007. Maximum Subsequence Sum测试通过,测试main函数如下
1 2 3 4 5 6 7 8 9 10 11 12 13 | int main() { int n; scanf ( "%d" , &n); vector< int >vec(n); for ( int i = 0; i < n; i++) scanf ( "%d" , &vec[i]); int left, right; int maxsum = maxSum1(vec, left, right); //测试时替换函数名称 if (maxsum >= 0) printf ( "%d %d %d" , maxsum, vec[left], vec[right]); else printf ( "0 %d %d" , vec[0], vec[n-1]); } |
参考:编程之美2.14 求数组的子数组之和的最大值
算法1:最简单的就是穷举所有的子数组,然后求和,复杂度是O(n^3)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | int maxSum1(vector< int >&vec, int &left, int &right) { int maxsum = INT_MIN, sum = 0; for ( int i = 0; i < vec.size(); i++) for ( int k = i; k < vec.size(); k++) { sum = 0; for ( int j = i; j <= k; j++) sum += vec[j]; if (sum > maxsum) { maxsum = sum; left = i; right = k; } } return maxsum; } |
算法2: 上面代码第三重循环做了很多的重复工作,稍稍改进如下,复杂度为O(n^2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | int maxSum2(vector< int >&vec, int &left, int &right) { int maxsum = INT_MIN, sum = 0; for ( int i = 0; i < vec.size(); i++) { sum = 0; for ( int k = i; k < vec.size(); k++) { sum += vec[k]; if (sum > maxsum) { maxsum = sum; left = i; right = k; } } } return maxsum; } |
算法3: 分治法, 下面贴上编程之美的解释, 复杂度为O(nlogn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | //求数组vec【start,end】的最大子数组和,最大子数组边界为[left,right] int maxSum3(vector< int >&vec, const int start, const int end, int &left, int &right) { if (start == end) { left = start; right = left; return vec[start]; } int middle = start + ((end - start)>>1); int lleft, lright, rleft, rright; int maxLeft = maxSum3(vec, start, middle, lleft, lright); //左半部分最大和 int maxRight = maxSum3(vec, middle+1, end, rleft, rright); //右半部分最大和 int maxLeftBoeder = vec[middle], maxRightBorder = vec[middle+1], mleft = middle, mright = middle+1; int tmp = vec[middle]; for ( int i = middle-1; i >= start; i--) { tmp += vec[i]; if (tmp > maxLeftBoeder) { maxLeftBoeder = tmp; mleft = i; } } tmp = vec[middle+1]; for ( int i = middle+2; i <= end; i++) { tmp += vec[i]; if (tmp > maxRightBorder) { maxRightBorder = tmp; mright = i; } } int res = max(max(maxLeft, maxRight), maxLeftBoeder+maxRightBorder); if (res == maxLeft) { left = lleft; right = lright; } else if (res == maxLeftBoeder+maxRightBorder) { left = mleft; right = mright; } else { left = rleft; right = rright; } return res; } |
算法4: 动态规划, 数组为vec[],设dp[i] 是以vec[i]结尾的子数组的最大和,对于元素vec[i+1], 它有两种选择:a、vec[i+1]接着前面的子数组构成最大和,b、vec[i+1]自己单独构成子数组。则dp[i+1] = max{dp[i]+vec[i+1], vec[i+1]}
如果不考虑记录最大子数组的位置,于是有以下代码: 本文地址
1 2 3 4 5 6 7 8 9 10 | int maxSum_(vector< int >&vec) { int maxsum = INT_MIN, sum = 0; for ( int i = 0; i < vec.size(); i++) { sum = max(sum + vec[i], vec[i]); maxsum = max(maxsum, sum); } return maxsum; } |
对以上代码换个写法,并记录最大子数组的位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | int maxSum4(vector< int >&vec, int &left, int &right) { int maxsum = INT_MIN, sum = 0; int begin = 0; for ( int i = 0; i < vec.size(); i++) { if (sum >= 0) { sum += vec[i]; } else { sum = vec[i]; begin = i; } if (maxsum < sum) { maxsum = sum; left = begin; right = i; } } return maxsum; } |
如果数组是循环的,该如何呢
这时分两种情形(图中红色方框表示求得的最大子数组,left、right分别是子数组的开始和结尾):
(1)如下图最大的子数组没有跨过vec[n-1]到vec[0], 这就是每循环的情况
(2)如下图,最大的子数组跨过vec[n-1]到vec[0]
对于第二种情形,相当于从原数组中挖掉了一块(vec[right+1], …, vec[left-1]) ,那么我们只要使挖掉的和最小即可,求最小子数组和最大子数组类似,代码如下,以下代码在九度oj1572首尾相连数组的最大子数组和通过测试(测试需要,以下代码当数组全是负数时,输出0):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | int maxSumCycle(vector< int >&vec, int &left, int &right) { int maxsum = INT_MIN, curMaxSum = 0; int minsum = INT_MAX, curMinSum = 0; int sum = 0; int begin_max = 0, begin_min = 0; int minLeft, minRight; for ( int i = 0; i < vec.size(); i++) { sum += vec[i]; if (curMaxSum >= 0) { curMaxSum += vec[i]; } else { curMaxSum = vec[i]; begin_max = i; } if (maxsum < curMaxSum) { maxsum = curMaxSum; left = begin_max; right = i; } ///////////////求和最小的子数组 if (curMinSum <= 0) { curMinSum += vec[i]; } else { curMinSum = vec[i]; begin_min = i; } if (minsum > curMinSum) { minsum = curMinSum; minLeft = begin_min; minRight = i; } } if (maxsum >= sum - minsum) return maxsum; else { left = minRight+1; right = minLeft-1; return sum - minsum; } } |
参考:面试题精解之二: 字符串、数组(1)
【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3698246.html