当前位置:网站首页>LeetCode 1031. Maximum sum of two non overlapping subarrays
LeetCode 1031. Maximum sum of two non overlapping subarrays
2022-07-07 16:58:00 【@Little safflower】
Problem description
Give an array of nonnegative integers A , Return two non overlapping ( continuity ) The maximum sum of elements in a subarray , The length of the subarray is L and M.( What needs to be clarified here is , Long for L The subarray of can appear at length as M Before or after the subarray of .)
In form , Return to the biggest V, and V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) And meet one of the following conditions :
0 <= i < i + L - 1 < j < j + M - 1 < A.length, or
0 <= 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
explain : In a selection of subarrays ,[9] The length is 1,[6,5] The length is 2.
Example 2:Input :A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
Output :29
explain : In a selection of subarrays ,[3,8,1] The length is 3,[8,9] The length is 2.
Example 3:Input :A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
Output :31
explain : In a selection of subarrays ,[5,6,0,9] The length is 4,[0,3,8] The length is 3.
Tips :
L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000source : Power button (LeetCode)
link :https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
java
class Solution {
public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
int n = nums.length;
// The prefix and
int[] sum = new int[n + 1];
for(int i = 0;i < n;i++){
sum[i + 1] = sum[i] + nums[i];
}
// In exchange for
if(firstLen > secondLen){
firstLen ^= secondLen;
secondLen ^= firstLen;
firstLen ^= secondLen;
}
int[][] dp = new int[n + 1][2];
int ans = 0;
// From firstLen Start
for(int i = firstLen;i <= n;i++){
// The current element has been closed before firstLen And
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;
}
}
边栏推荐
猜你喜欢
Spark Tuning (III): persistence reduces secondary queries
值得一看,面试考点与面试技巧
面向接口编程
【MySql进阶】索引详解(一):索引数据页结构
Horizontal and vertical centering method and compatibility
Binary search tree (basic operation)
字节跳动Android面试,知识点总结+面试题解析
QT中自定义控件的创建到封装到工具栏过程(二):自定义控件封装到工具栏
字节跳动Android金三银四解析,android面试题app
AutoLISP series (3): function function 3
随机推荐
Set the route and optimize the URL in thinkphp3.2.3
【Seaborn】组合图表、多子图的实现
【DesignMode】享元模式(Flyweight Pattern)
LeetCode 152. 乘积最大子数组 每日一题
Prediction - Grey Prediction
Imitate the choice of enterprise wechat conference room
LeetCode 1986. 完成任务的最少工作时间段 每日一题
As an Android Developer programmer, Android advanced interview
node:504报错
[designmode] template method pattern
谎牛计数(春季每日一题 53)
URL和URI的关系
os、sys、random标准库主要功能
作为Android开发程序员,android高级面试
【医学分割】attention-unet
Personal notes of graphics (2)
数据中台落地实施之法
Read PG in data warehouse in one article_ stat
Advanced C language -- function pointer
使用JSON.stringify()去实现深拷贝,要小心哦,可能有巨坑