[leetcode] 1031. Maximum Sum of Two Non-Overlapping Subarrays

[leetcode] 1031. Maximum Sum of Two Non-Overlapping Subarrays

Description

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 = 2Output: 20Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Example 2:

Input: A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2Output: 29Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Example 3:

Input: A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3Output: 31Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.

Note:

L >= 1M >= 1L + M <= A.length <= 10000 <= A[i] <= 1000

分析

题目的意思是：给你一个数组，求取出L长度的子数组和M长度的子数组，两数组不相交，这道题我不会，找了一个我能看懂的解法，首先是建立一个求和的数组，然后再构造题目中说的两种情况，找出最大值就行了，注意两次遍历的取的遍历区间，特别是n+1,n+1代表的是prefix数组的长度哈，因为最开始加了一个0哈。

代码

class Solution: def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int: n=len(A) prefix=[0] for i in range(n): t=prefix[-1]+A[i] prefix.append(t) maxl=maxm=0 summ=0 for i in range(M,n+1-L): maxm=max(maxm,prefix[i]-prefix[i-M]) summ=max(summ,maxm+prefix[i+L]-prefix[i]) for i in range(L,n+1-M): maxl=max(maxl,prefix[i]-prefix[i-L]) summ=max(summ,maxl+prefix[i+M]-prefix[i]) return summ

参考文献

​​[LeetCode] Python, clean O(N), 98%​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。