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-M~i的和是M子数组的和,l_max保存0~i-M中最大的L长度子数组的和
  2. M出现在L之前,即i-L~i的和是L子数组的和,m_max保存0~i-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;
    }
    };