原题说明
Given an array A
of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths L
and M
. (For clarification, the L-length subarray could occur before or after the M-length subarray.)
Formally, return the largest V
for which V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1])
and either:0 <= i < i + L - 1 < j < j + M - 1 < A.length
, or0 <= j < j + M - 1 < i < i + L - 1 < A.length
.
Example 1:
Input:
A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
Output:20
Explanation: One choice of subarrays is[9]
with length1
, and[6,5]
with length2
.
Example 2:
Input:
A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
Output:29
Explanation: One choice of subarrays is[3,8,1]
with length3
, and[8,9]
with length2
.
Example 3:
Input:
A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
Output:31
Explanation: One choice of subarrays is[5,6,0,9]
with length4
, and[3,8]
with length3
.
Note:
L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000
解题思路
动态规划
凡是要求数组某一段的和,要想到用pre_sum
,pre_sum[i]
表示指数i
之前左右数的和。
这样我们要求A[i]
到A[j]
之间所有数的和,就可以用pre_sum[j] - pre_sum[i - 1]
回到这道题,我们第一遍遍历数组A求pre_sum。
第二遍遍历,指数为i
,用max_L
记录指数i - M
之前的最大连续L
个数之和,
每次更新max_L
为max(max_L, pre_sum[i - M] - pre_sum[i - L - M])
max_L + pre_sum[i] - pre_sum[i - M]
表示以i
结尾最后连续M
个数,与之前最大的连续L
个数的和。
同理max_M + pre_sum[i] - pre_sum[i - L]
就表示以i结尾最后连续L
个数,与之前最大的连续M
个数的和。
取其中较大的与最终要返回的值res
比较,并更新即可。
示例代码 (cpp)
1 | class Solution { |
示例代码 (java)
1 | class Solution { |
示例代码 (python)
1 | class Solution(object): |
复杂度分析
时间复杂度: O(N)
空间复杂度: O(N)
归纳总结
我们在Youtube上更新了视频讲解,欢迎关注!