当前位置:网站首页>LeetCode 1043. Separate the array to get the maximum and daily questions
LeetCode 1043. Separate the array to get the maximum and daily questions
2022-07-07 16:58:00 【@Little safflower】
Problem description
Give you an array of integers arr, Please separate the array into at most k Some of ( continuity ) Subarray . After separation , All values in each subarray will become the maximum value in that subarray .
Returns the maximum sum of elements that can be obtained after separating and transforming the array .
Be careful , The corresponding order of the original array and the separated array should be the same , in other words , You can only choose the position of the separated array, but you can't adjust the order in the array .
Example 1:
Input :arr = [1,15,7,9,2,5,10], k = 3
Output :84
explain :
because k=3 Can be separated into [1,15,7] [9] [2,5,10], The result is [15,15,15,9,10,10,10], And for 84, Is the largest sum of all elements of the array after separation and transformation .
If separated into [1] [15,7,9] [2,5,10], The result is [1, 15, 15, 15, 10, 10, 10] But the sum of the elements of this separation (76) Less than one .
Example 2:Input :arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output :83
Example 3:Input :arr = [1], k = 1
Output :1
Tips :
1 <= arr.length <= 500
0 <= arr[i] <= 109
1 <= k <= arr.lengthsource : Power button (LeetCode)
link :https://leetcode.cn/problems/partition-array-for-maximum-sum
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 maxSumAfterPartitioning(int[] arr, int k) {
int n = arr.length;
int[] dp = new int[n];
for(int i = 0;i < k;i++){
dp[i] = getMaxValue(arr,0,i) * (i + 1);
}
for(int i = k;i < n;i++){
for(int j = 1;j <= k;j++){
dp[i] = Math.max(dp[i],dp[i - j] + getMaxValue(arr,i - j + 1,i) * j);
}
}
return dp[n - 1];
}
// Get the maximum value of the specified interval
public int getMaxValue(int[] arr,int left,int right){
int ans = 0;
for(int i = left;i <= right;i++){
ans = Math.max(ans,arr[i]);
}
return ans;
}
}
边栏推荐
- 【DesignMode】外观模式 (facade patterns)
- typescript ts基础知识之tsconfig.json配置选项
- Laravel5.1 Routing - routing packets
- AutoLISP series (2): function function 2
- 二叉搜索树(基操篇)
- 字节跳动Android金三银四解析,android面试题app
- skimage学习(1)
- three. JS create cool snow effect
- URL和URI的关系
- Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
猜你喜欢
掌握这个提升路径,面试资料分享
【DesignMode】代理模式(proxy pattern)
Master this promotion path and share interview materials
Cesium(3):ThirdParty/zip. js
如何快速检查钢网开口面积比是否符合 IPC7525
QML初学
Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
C语言进阶——函数指针
【图像传感器】相关双采样CDS
字节跳动Android面试,知识点总结+面试题解析
随机推荐
LeetCode-SQL第一天
"The" "PIP" "entry cannot be recognized as the name of a cmdlet, function, script file, or runnable program."
应用在温度检测仪中的温度传感芯片
3000 words speak through HTTP cache
Build an all in one application development platform, light flow, and establish a code free industry benchmark
直接上干货,100%好评
A tour of gRPC:03 - proto序列化/反序列化
【Seaborn】组合图表:FacetGrid、JointGrid、PairGrid
面试题 01.02. 判定是否互为字符重排-辅助数组算法
《产品经理必读:五种经典的创新思维模型》的读后感
Introduction to ThinkPHP URL routing
ByteDance Android gold, silver and four analysis, Android interview question app
Cesium (4): the reason why gltf model is very dark after loading
JS中null NaN undefined这三个值有什么区别
Opportunity interview experience summary
QT视频传输
QT 图片背景色像素处理法
最新高频Android面试题目分享,带你一起探究Android事件分发机制
Three. JS series (3): porting shaders in shadertoy
DNS 系列(一):为什么更新了 DNS 记录不生效?