1043. 分隔数组以得到最大和

发表于 分类于 阅读次数： Waline： 本文字数： 119 阅读时长 ≈ 1 分钟

考点

  • 划分DP

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int maxSumAfterPartitioning(vector<int>& arr, int k) {
    int a[505], f[505];
    int n = arr.size();
    for (int i = 1; i <= n; ++i) a[i] = arr[i - 1];
    memset(f, 0xcf, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      int mx = -1;
      for (int j = i; j >= max(1, i + 1 - k); --j) {
        mx = max(mx, a[j]);
        f[i] = max(f[i], (i - j + 1) * mx + f[j - 1]);
      }
    }
    return f[n];
  }
};

思路

划分DP的裸题，不再赘述，以当前数字为结尾，枚举其所在的子数组即可