题目描述：
给出一个整数数组 $arr$ ，长度为 $n$ ，将该数组分隔为长度最多为 $k$ 的一些连续子数组。分隔完毕之后，每个子数组中的所有数都会变成该子数组中的最大值。
数据范围：
$1\le n \le 500;0\le arr[i] \le 10^9;1\le k \le n$
题解：
使用 $dp[i]$ 表示前 $i$ 个能得到的最大值，那么 $dp[i] = dp[j] + max \times (i - j), j \in [i - k, i - 1]$ ，其中 $max = max(arr[i]), i \in [j + 1, i]$ 倒着枚举 $j$ 时刚好可以维护子区间最大值。考虑初始化，如果使用 $[0,n-1]$ 作为下标，那么需要提前处理出 $dp[i], i\in[0, k - 1]$ 。因为下标为 $[1,n]$ 时， $dp[i]$ 可以从 $dp[0]$ 更新，但是下标为 $[0, n - 1]$ 时， $dp[i]$ 从 $dp[0]$ 更新时取得最大值是 $max(arr[i]), i \in [1, i]$ ，少了 $arr[0]$ ，因为不能从 $dp[-1]$ 更新，因此需要单独初始化。还是直接使用 $[1,n]$ 作为 $dp$ 下标比较方便。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution
{
public:
int maxSumAfterPartitioning(vector<int> &arr, int k)
{
int n = arr.size();
vector<int> dp(n + 1, 0);
int maxx = -1;
for (int i = 1; i <= n; ++i)
{
maxx = arr[i - 1];
for (int j = i - 1; j >= i - k && j >= 0; --j)
{
maxx = max(arr[(j + 1) - 1], maxx);
dp[i] = max(dp[i], dp[j] + maxx * (i - j));
}
}
return dp[n];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution
{
public:
int maxSumAfterPartitioning(vector<int> &arr, int k)
{
int n = arr.size();
vector<int> dp(n, 0);
int maxx = -1;
for (int i = 0; i < k; ++i)
{
maxx = max(maxx, arr[i]);
dp[i] = (i + 1) * maxx;
}
for (int i = k; i < n; ++i)
{
maxx = arr[i];
for (int j = i - 1; j >= max(i - k, 0); --j)
{
maxx = max(arr[j + 1], maxx);
dp[i] = max(dp[i], dp[j] + maxx * (i - j));
}
}
return dp[n - 1];
}
};
|