当前位置:网站首页>LeetCode 1043. 分隔数组以得到最大和 每日一题
LeetCode 1043. 分隔数组以得到最大和 每日一题
2022-07-07 15:32:00 【@小红花】
问题描述
给你一个整数数组 arr,请你将该数组分隔为长度最多为 k 的一些(连续)子数组。分隔完成后,每个子数组的中的所有值都会变为该子数组中的最大值。
返回将数组分隔变换后能够得到的元素最大和。
注意,原数组和分隔后的数组对应顺序应当一致,也就是说,你只能选择分隔数组的位置而不能调整数组中的顺序。
示例 1:
输入:arr = [1,15,7,9,2,5,10], k = 3
输出:84
解释:
因为 k=3 可以分隔成 [1,15,7] [9] [2,5,10],结果为 [15,15,15,9,10,10,10],和为 84,是该数组所有分隔变换后元素总和最大的。
若是分隔成 [1] [15,7,9] [2,5,10],结果就是 [1, 15, 15, 15, 10, 10, 10] 但这种分隔方式的元素总和(76)小于上一种。
示例 2:输入:arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出:83
示例 3:输入:arr = [1], k = 1
输出:1
提示:
1 <= arr.length <= 500
0 <= arr[i] <= 109
1 <= k <= arr.length来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/partition-array-for-maximum-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
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];
}
//得到指定区间的最大值
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;
}
}
边栏推荐
- [vulnhub range] thales:1
- Imitate the choice of enterprise wechat conference room
- Prediction - Grey Prediction
- Usage of config in laravel
- 打造All-in-One应用开发平台,轻流树立无代码行业标杆
- 水平垂直居中 方法 和兼容
- 深度监听 数组深度监听 watch
- 无法将“pip”项识别为 cmdlet、函数、脚本文件或可运行程序的名称
- Talk about the realization of authority control and transaction record function of SAP system
- Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
猜你喜欢
ByteDance Android gold, silver and four analysis, Android interview question app
Master this promotion path and share interview materials
数据中台落地实施之法
最新Android面试合集,android视频提取音频
1亿单身男女“在线相亲”,撑起130亿IPO
Lowcode: four ways to help transportation companies enhance supply chain management
字节跳动高工面试,轻松入门flutter
Horizontal and vertical centering method and compatibility
spark调优(三):持久化减少二次查询
Temperature sensor chip used in temperature detector
随机推荐
一文读懂数仓中的pg_stat
【C 语言】 题集 of Ⅹ
DNS 系列(一):为什么更新了 DNS 记录不生效?
Tragedy caused by deleting the console statement
【PHP】PHP接口继承及接口多继承原理与实现方法
字节跳动Android金三银四解析,android面试题app
URL和URI的关系
spark调优(三):持久化减少二次查询
laravel构造函数和中间件执行顺序问题
Balanced binary tree (AVL)
[medical segmentation] attention Unet
How does laravel run composer dump autoload without emptying the classmap mapping relationship?
【HCSD大咖直播】亲授大厂面试秘诀-简要笔记
华东师大团队提出,具有DNA调控电路的卷积神经网络的系统分子实现
Direct dry goods, 100% praise
最新阿里P7技术体系,妈妈再也不用担心我找工作了
如何快速检查钢网开口面积比是否符合 IPC7525
字节跳动Android面试,知识点总结+面试题解析
Introduction and use of gateway
【DesignMode】模板方法模式(Template method pattern)