当前位置:网站首页>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;
}
}
边栏推荐
- 打造All-in-One应用开发平台,轻流树立无代码行业标杆
- AutoLISP series (1): function function 1
- Tidb cannot start after modifying the configuration file
- 模块六
- LeetCode 300. 最长递增子序列 每日一题
- Advanced C language -- function pointer
- Set the route and optimize the URL in thinkphp3.2.3
- LeetCode 1654. 到家的最少跳跃次数 每日一题
- LeetCode-SQL第一天
- Ray and OBB intersection detection
猜你喜欢
记录Servlet学习时的一次乱码
node:504报错
ByteDance Android gold, silver and four analysis, Android interview question app
Skimage learning (3) -- gamma and log contrast adjustment, histogram equalization, coloring gray images
QML初学
正在准备面试,分享面经
应用在温度检测仪中的温度传感芯片
[Android -- data storage] use SQLite to store data
面向接口编程
null == undefined
随机推荐
SqlServer2014+: 创建表的同时创建索引
typescript ts基础知识之tsconfig.json配置选项
Three. JS series (2): API structure diagram-2
LeetCode 1031. 两个非重叠子数组的最大和 每日一题
全网“追杀”钟薛高
最新Android面试合集,android视频提取音频
Prediction - Grey Prediction
运算符
最新Android高级面试题汇总,Android面试题及答案
23. 合并K个升序链表-c语言
LeetCode 1986. 完成任务的最少工作时间段 每日一题
直接上干货,100%好评
【图像传感器】相关双采样CDS
蓝桥杯 决赛 异或变换 100分
Record the migration process of a project
LeetCode 1155. 掷骰子的N种方法 每日一题
Module VI
QML初学
Localstorage and sessionstorage
二叉搜索树(特性篇)