当前位置:网站首页>LeetCode 1031. 两个非重叠子数组的最大和 每日一题
LeetCode 1031. 两个非重叠子数组的最大和 每日一题
2022-07-07 15:32:00 【@小红花】
问题描述
给出非负整数数组 A ,返回两个非重叠(连续)子数组中元素的最大和,子数组的长度分别为 L 和 M。(这里需要澄清的是,长为 L 的子数组可以出现在长为 M 的子数组之前或之后。)
从形式上看,返回最大的 V,而 V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并满足下列条件之一:
0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或
0 <= j < j + M - 1 < i < i + L - 1 < A.length.
示例 1:
输入:A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
输出:20
解释:子数组的一种选择中,[9] 长度为 1,[6,5] 长度为 2。
示例 2:输入:A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
输出:29
解释:子数组的一种选择中,[3,8,1] 长度为 3,[8,9] 长度为 2。
示例 3:输入:A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
输出:31
解释:子数组的一种选择中,[5,6,0,9] 长度为 4,[0,3,8] 长度为 3。
提示:
L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
java
class Solution {
public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
int n = nums.length;
//前缀和
int[] sum = new int[n + 1];
for(int i = 0;i < n;i++){
sum[i + 1] = sum[i] + nums[i];
}
//交换
if(firstLen > secondLen){
firstLen ^= secondLen;
secondLen ^= firstLen;
firstLen ^= secondLen;
}
int[][] dp = new int[n + 1][2];
int ans = 0;
//从第firstLen开始
for(int i = firstLen;i <= n;i++){
//已当前元素为结束的前firstLen的和
int s1 = sum[i] - sum[i - firstLen];
dp[i][0] = Math.max(dp[i - 1][0],s1);
ans = Math.max(ans,s1 + dp[i - firstLen][1]);
if(i >= secondLen){
int s2 = sum[i] - sum[i - secondLen];
dp[i][1] = Math.max(dp[i - 1][1],s2);
ans = Math.max(ans,s2 + dp[i - secondLen][0]);
}
}
return ans;
}
}
边栏推荐
- 低代码(lowcode)帮助运输公司增强供应链管理的4种方式
- The difference and working principle between compiler and interpreter
- 模拟Servlet的本质
- 【Android -- 数据存储】使用 SQLite 存储数据
- 面试题 01.02. 判定是否互为字符重排-辅助数组算法
- The team of East China Normal University proposed the systematic molecular implementation of convolutional neural network with DNA regulation circuit
- 华东师大团队提出,具有DNA调控电路的卷积神经网络的系统分子实现
- 打造All-in-One应用开发平台,轻流树立无代码行业标杆
- Master this promotion path and share interview materials
- Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
猜你喜欢
Statistical learning method -- perceptron
The difference and working principle between compiler and interpreter
【Vulnhub靶场】THALES:1
Opencv personal notes
Talk about the realization of authority control and transaction record function of SAP system
Interface oriented programming
Temperature sensor chip used in temperature detector
AutoLISP series (3): function function 3
记录Servlet学习时的一次乱码
DNS 系列(一):为什么更新了 DNS 记录不生效?
随机推荐
Sort out several important Android knowledge and advanced Android development interview questions
作为Android开发程序员,android高级面试
logback.xml配置不同级别日志,设置彩色输出
47_ Contour lookup in opencv cv:: findcontours()
DAPP defi NFT LP single and dual currency liquidity mining system development details and source code
Vs2019 configuration matrix library eigen
【DesignMode】模板方法模式(Template method pattern)
模块六
Pycharm terminal enables virtual environment
JS中null NaN undefined这三个值有什么区别
JS modularization
Record the migration process of a project
Cesium (4): the reason why gltf model is very dark after loading
Read PG in data warehouse in one article_ stat
Imitate the choice of enterprise wechat conference room
偶然升职的内心独白
Deep listening array deep listening watch
字节跳动高工面试,轻松入门flutter
Sqlserver2014+: create indexes while creating tables
[vulnhub range] thales:1