【leetcode】1031. Maximum Sum of Two Non-Overlapping Subarrays
2024-08-24 12:58:41
题目如下:
Given an array
A
of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengthsL
andM
. (For clarification, theL
-length subarray could occur before or after theM
-length subarray.)Formally, return the largest
V
for whichV = (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 length 1, and [6,5] with length 2.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 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 = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.Note:
L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000
解题思路:A的长度最大只有1000,表示O(n^2)的复杂度可以接受,那么直接用嵌套的两个循环暴力计算吧。
代码如下:
class Solution(object):
def maxSumTwoNoOverlap(self, A, L, M):
"""
:type A: List[int]
:type L: int
:type M: int
:rtype: int
"""
val = []
count = 0
for i in range(len(A)):
count += A[i]
val.append(count) res = 0
for i in range(len(A)-L+1):
for j in range(len(A)-M+1):
if i == 0 and j == 2:
pass
if (j+M-1) < i or (i+L-1) < j:
v2 = val[j+M-1]
if j>=1:
v2 -= val[j-1]
v1 = val[i+L-1]
if i >= 1:
v1 -= val[i - 1]
res = max(res, v1 + v2)
return res
最新文章
- 【codevs1106】 篝火晚会
- iOS开发——UI进阶篇(五)通知、代理、kvo的应用和对比,购物车
- Sqoop_mysql,hive,hdfs导入导出操作
- 白话学习MVC(十)View的呈现二
- Windows:常见问题
- 2015 ";BestCoder Cup"; Champion
- QT添加程序图标及窗口图标
- 烂泥:KVM安装centos6.5系统
- PostgreSQL auto_explain
- Java中的blank final
- ISO7816协议的块传输协议
- React-Native post和get请求
- Android studio教程:[6]创建多个Activity
- 数据库sqlite的使用
- HBase数据存储格式
- 通过Elasticsearch使用的你的数据
- jQuery代码优化的9种方法
- tomcat环境多个jdk版本自定义使用JDK版本及路径
- Python中Queue模块及多线程使用
- 视角同步NewViewTarget
热门文章
- Linux驱动开发2——字符设备驱动
- fatal: repository &#39;xxxx&#39; not found
- python上下文管理,with语句
- Delphi XE2 之 FireMonkey 入门(10) - 常用结构 TPoint、TPointF、TSmallPoint、TSize、TRect、TRectF 及相关方法
- 阶段1 语言基础+高级_1-3-Java语言高级_09-基础加强_第1节 基础加强_4_Junit_@Before&;@After
- jmeter接口测试初体验
- 错误:Only the original thread that created a view hierarchy can touch its views——Handler的使用
- Vue Router:使用 props 将组件和路由解耦
- python 正则表达式 re.match
- vue通信之子父组件通信