最大子数组问题及其扩展

给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
样例
给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6

挑战
要求时间复杂度为O(n)
解答

    int maxSubArray(vector<int> &nums) {
        int maxSum = nums[0];
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (sum < 0) {
                sum = 0;
                maxSum = nums[i] > maxSum ? nums[i] : maxSum;
            } else {
                maxSum = sum > maxSum ? sum : maxSum;
            }
        }
        return maxSum;
    }

扩展
描述
给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。

子数组最少包含一个数

样例
给出数组 [1, 3, -1, 2, -1, 2]
这两个子数组分别为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]，它们的最大和都是 7

挑战
要求时间复杂度为 O(n)

方法一：
以第i个元素为边界，将数组分为前后两部分，分别计算前一部分和后一部分的最大子数组和，再将两个和相加，最后从这些和里面找到一个最大的和
这种解法每一种情况的复杂度数O(N)，N-1种情况的复杂度为O(N^2)。

int maxTwoSubArrays(vector<int> &nums) {
        int maxSum;
        for (int i = 0; i < nums.size() - 1; i++) {
            int preMax = maxSubArray(nums, 0, i);
            int index = i + 1 < nums.size() ? i + 1 : nums.size() - 1;
            int postMax = maxSubArray(nums, index, nums.size() - 1);
            int sum = preMax + postMax;
            if (i == 0) {
                maxSum = sum;
            } else {
                maxSum = sum > maxSum ? sum : maxSum;
            }
        }
    
        return maxSum;
    }
    
    int maxSubArray(vector<int> &nums, int begin, int end) {
        int maxSum = nums[begin];
        int sum = 0;
        for (int i = begin; i <= end; i++) {
            sum += nums[i];
            if (sum < 0) {
                sum = 0;
                maxSum = nums[i] > maxSum ? nums[i] : maxSum;
            } else {
                maxSum = sum > maxSum ? sum : maxSum;
            }
        }
        return maxSum;
    }

方法二：采用动态规划的思想
方法一中的每种情况都存在重复计算的情况，考虑使用空间换时间的方案，将计算的中间结果保存下来
创建两个数组，pre[i]记录前一部分0~i时的最大的子数组和，post[i]记录后一部分的最大子数组和，通过求最大的pre[i] + post[size - i - 1]得到最大的和。

int maxTwoSubArrays(vector<int> &nums) {
        vector<int> pre;
        maxPreSubArrays(nums, pre);
        
        vector<int> post;
        maxPostSubArrays(nums, post);
        
        int maxSum = pre[0] + post[pre.size() - 1];
        for (int i = 0; i < pre.size(); i++) {
            int sum = pre[i] + post[pre.size() - 1 - i];
            maxSum = sum > maxSum ? sum : maxSum;
        }
        return maxSum;
    }
    
    int maxPreSubArrays(vector<int> &nums, vector<int> &pre) {
        int maxSum = nums[0];
        int sum = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            sum += nums[i];
            if (sum < 0) {
                sum = 0;
                maxSum = nums[i] > maxSum ? nums[i] : maxSum;
            } else {
                maxSum = sum > maxSum ? sum : maxSum;
            }
            pre.push_back(maxSum);
        }
    }
    
    int maxPostSubArrays(vector<int> &nums, vector<int> &post) {
        int maxSum = nums[nums.size() - 1];
        int sum = 0;
        for (int i = nums.size() - 1; i > 0; i--) {
            sum += nums[i];
            if (sum < 0) {
                sum = 0;
                maxSum = nums[i] > maxSum ? nums[i] : maxSum;
            } else {
                maxSum = sum > maxSum ? sum : maxSum;
            }
            post.push_back(maxSum);
        }
    }

算法导论：当问题具有最优子结构和重叠子问题时，可以考虑用动态规划算法。动态规划方法安排求解顺序，对每个子问题只求解一次，并将结果保存下来。如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算。因此动态规划算法是付出额外的内存空间来节省计算时间，是典型的时空权衡的例子。