hyz's blog
0%

发表于

题意

题目链接：Maximum Subarray

给一个数组，求该数组的最大子数组和。

思路

解法1：从左到右遍历一次，累加，若sum比现有的答案大，则更新。若sum为负数，则放弃这一段的元素，置为0。时间复杂度为O(n)，空间复杂度为O(1)。

解法2：分治法。若我们将一个数组从中间分隔成两个数组，则它的答案是max(左数组的答案, 右数组的答案, 左数组的最大后缀和+右数组的最大前缀和+中间元素)。时间复杂度为O(nlogn)，空间复杂度为O(logn)。

代码

解法1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        long long ans = LONG_LONG_MIN;
        long long sum = 0;
        for (auto i: nums) {
            sum += i;
            if (sum > ans)
                ans = sum;
            if (sum < 0)
                sum = 0;
        }
        return ans;
    }
};

解法2：

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
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int l = 0, r = nums.size();
        return maxSubArrayCore(nums, l, r);
    }
private:
    int maxSubArrayCore(vector<int>& nums, int l, int r) {
        if (l >= r) {
            return INT_MIN;
        }
        int mid = l + ((r - l) >> 1);

        int leftMax = 0;
        for (int i = mid - 1, sum = 0; i >= l; i--) {
            sum += nums[i];
            leftMax = max(leftMax, sum);
        }

        int rightMax = 0;
        for (int i = mid + 1, sum = 0; i < r; i++) {
            sum += nums[i];
            rightMax = max(rightMax, sum);
        }

        return max(leftMax + rightMax + nums[mid],
                max(maxSubArrayCore(nums, l, mid), maxSubArrayCore(nums, mid + 1, r)));
    }
};