当前位置:网站首页>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;
}
}
边栏推荐
- Arduino 控制的双足机器人
- Opencv personal notes
- 谎牛计数(春季每日一题 53)
- Tidb cannot start after modifying the configuration file
- 【图像传感器】相关双采样CDS
- Advanced C language -- function pointer
- [C language] question set of X
- 打造All-in-One应用开发平台,轻流树立无代码行业标杆
- 面试题 01.02. 判定是否互为字符重排-辅助数组算法
- [Android -- data storage] use SQLite to store data
猜你喜欢
最新Android高级面试题汇总,Android面试题及答案
【MySql进阶】索引详解(一):索引数据页结构
Lowcode: four ways to help transportation companies enhance supply chain management
【医学分割】attention-unet
Personal notes of graphics (1)
Horizontal and vertical centering method and compatibility
如何快速检查钢网开口面积比是否符合 IPC7525
直接上干货,100%好评
记一次项目的迁移过程
C语言进阶——函数指针
随机推荐
两类更新丢失及解决办法
Personal notes of graphics (2)
Find tags in prefab in unity editing mode
DNS 系列(一):为什么更新了 DNS 记录不生效?
PHP has its own filtering and escape functions
Vs2019 configuration matrix library eigen
【PHP】PHP接口继承及接口多继承原理与实现方法
预测——灰色预测
Deep listening array deep listening watch
Ray and OBB intersection detection
Arduino 控制的双足机器人
AutoLISP series (3): function function 3
Binary search tree (basic operation)
AutoLISP series (1): function function 1
AutoLISP series (2): function function 2
【DesignMode】代理模式(proxy pattern)
作为Android开发程序员,android高级面试
Inner monologue of accidental promotion
ATM系统
The difference and working principle between compiler and interpreter