LeetCode 1043. Partition Array for Maximum Sum
原题链接在这里:https://leetcode.com/problems/partition-array-for-maximum-sum/
题目:
Given an integer array A
, you partition the array into (contiguous) subarrays of length at most K
. After partitioning, each subarray has their values changed to become the maximum value of that subarray.
Return the largest sum of the given array after partitioning.
Example 1:
Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]
Note:
1 <= K <= A.length <= 500
0 <= A[i] <= 10^6
题解:
When encounter such kind of problem.
Could think from a simpler example. Say only one element, then 2 elements and more. Virtualize them, find routines.
Use array dp to memorize maxmimum sum up to i.
If, A = [1], then A becomes A[1]. dp = [1].
A = [1, 15], then A becomes A[15, 15]. dp = [1, 30].
A = [1, 15, 7], then A becomes A[15, 15, 15]. dp = [1, 30, 45].
A = [1, 15, 7, 9], then A becomes A[15, 15, 15, 9]. dp = [1, 30, 45, 54].
...
The routine is like from i back k(<= K) steps, find the maxmimum element, curMax * k + dp[i-k](if available).
Finally return dp[A.length-1].
Time Complexity: O(n*K). n = A.length.
Space: O(n).
AC Java:
class Solution {
public int maxSumAfterPartitioning(int[] A, int K) {
int len = A.length;
int [] dp = new int[len];
for(int i = 0; i<len; i++){
dp[i] = Integer.MIN_VALUE;
int curMax = A[i]; for(int k = 1; k<=K & i-k+1>=0; k++){
curMax = Math.max(curMax, A[i-k+1]);
dp[i] = Math.max(dp[i], (i-k<0 ? 0 : dp[i-k]) + curMax*k);
}
} return dp[len-1];
}
}
最新文章
- HTML 5 音频
- Smart210学习记录------块设备
- ubuntu 如何卸载重装docker
- my97自定义事件
- 【设计模式】java设计模式总述及观察者模式
- MySQL GTID复制Slave跳过错误事务Id以及复制排错问题总结
- 15. Life Cycle of the Products 产品的生命周期
- Unity的Input输入
- 『转』统计一个日志文件里,单词出现频率的shell脚本
- PHP策略模式2
- 牛客网NOIP赛前集训营-提高组(第一场)A 中位数
- Web挂马方式整理
- Visio 画图去掉页边距(图形四周的空白区域)的解决办法
- Web API 源码剖析之默认配置(HttpConfiguration)
- 如何进行 Python性能分析,你才能如鱼得水?
- PostgreSQL的xlog实验一
- YS报警权限验证安全设计
- Error处理:/bin/bash^M: 坏的解释器: 没有该文件或目录(bad interpreter: No such file or directory)
- 【HDU4336】Card Collector (动态规划,数学期望)
- POJ3150—Cellular Automaton(循环矩阵)