https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays

题目解析

给一个数组A，在其中找到两个不重叠子数组i、j，使得这两个子数组的和最大，子数组i的长度为M、子数组j的长度为L。
题目的关键在于如何降低时间复杂度，因为分别找到i，j然后再求和，时间复杂度就是O(n^3)了。

方法1 O(n^2)

提前获得数组的和，这样使得时间复杂度降为O(n^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
class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
        vector<int> sums(A.size(), 0);
        sums[0] = A[0];
        for (int i = 1; i < A.size(); i++) {
            sums[i] = sums[i-1] + A[i];
        }
        int max_sum = INT_MIN;
        for (int i = 0; i+M-1 < A.size(); i++) {
            for (int j = 0; j+L-1 < i; j++) {
                int msum = sums[i+M-1] - sums[i] + A[i];
                int lsum = sums[j+L-1] - sums[j] + A[j];
                max_sum = max(max_sum, msum+lsum);
            }
            for (int j = i+M; j+L-1 < A.size(); j++) {
                int msum = sums[i+M-1] - sums[i] + A[i];
                int lsum = sums[j+L-1] - sums[j] + A[j];
                max_sum = max(max_sum, msum+lsum);
            }
        }
        return max_sum;
    }
};

方法2 O(n)

第二种方法保存，L长度子序列的最大和以及M长度子序列的最大和，每次遍历会出现下面的两种情况：

  1. L出现在M之前，即i-Mi的和是M子数组的和，l_max保存0i-M中最大的L长度子数组的和
  2. M出现在L之前，即i-Li的和是L子数组的和，m_max保存0i-L中最大的M长度子数组的和
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
        int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
            vector<int> sums(A.size(), 0);
            sums[0] = A[0];
            for (int i = 1; i < A.size(); i++) {
                sums[i] = sums[i-1] + A[i];
            }
            int l_max = sums[L-1];
            int m_max = sums[M-1];
            int max_sum = sums[L+M-1]; // 关键，保存L+M这样排列时的值
            for (int i = M+L; i < A.size(); i++) {
                l_max = max(l_max, sums[i-M]-sums[i-M-L]);
                m_max = max(m_max, sums[i-L]-sums[i-M-L]);
                max_sum = max(max_sum, max(l_max+sums[i]-sums[i-M], m_max+sums[i]-sums[i-L]));
            }
            return max_sum;
        }
    };