穷举 元素 sub cnblogs ++ 最大子数组和 分割 end 复杂度
问题描述:
给一个整数数组,求其所有子数组中和最大的子数组在所给整数数组的的起始位置与终点;
方法一:穷举每个子数组,时间复杂度为o(N2);
方法三:时间复杂度为O(N); 请自行查阅书籍;
方法二:
采用分治思想:
先将数组从中间(分割点)分成两部分(和最大子数组要么在其左边,要么在其右边,或者跨过分割点),先求出左边和最大的子数组,再求右边和最大的子数组,
然后求经过中间分隔点的最大子数组和
- #include < iostream > using namespace std;
- struct sub { //定义一个子数组起点,终点与其所有元素和
- int start;
- int end;
- int sum;
- };
- sub merge(sub sub1, int start, int end, int A[]) //
- {
- int leftSum = 0,
- rightSum = 0,
- leftPos = (start + end) / 2,
- rightPos = (start + end) / 2 + 1,
- leftMax = -10000,
- rightMax = -10000;
- for (int i = (start + end) / 2; i >= start; i--) {
- leftSum += A[i]; //求最大数组和的起点
- if (leftMax < leftSum) {
- leftPos = i;
- leftMax = leftSum;
- }
- }
- for (int i = (start + end) / 2; i <= end; i++) {
- rightSum += A[i];
- if (rightMax < rightSum) //求最大数组和的终点
- {
- rightPos = i;
- rightMax = rightSum;
- }
- }
- if (sub1.sum < (rightMax + leftMax)) {
- sub1.start = leftPos;
- sub1.end = rightPos;
- sub1.sum = (rightMax + leftMax);
- }
- return sub1;
- }
- sub recursion(int start, int end, int A[]) {
- sub sub1,
- sub2;
- if (start < end) {
- sub1 = recursion(start, (start + end) / 2, A);
- sub2 = recursion((start + end) / 2 + 1, end, A);
- sub1 = sub1.sum > sub2.sum ? sub1: sub2;
- return merge(sub1, start, end, A);
- }
- sub1.start = sub1.end = start;
- sub1.sum = A[start];
- return sub1;
- }
- int main() {
- int a[] = {
- 1,
- -5,
- 9,
- 8,
- -3,
- -6,
- 11
- };
- sub sub1 = recursion(0, 6, a);
- cout << sub1.start << " to " << sub1.end << " sum:" << sub1.sum << endl;
- }
分治——最大数组和
来源: http://www.bubuko.com/infodetail-2351168.html