410-分割数组的最大值

题目

https://leetcode.cn/problems/split-array-largest-sum/description/

解答

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, LLONG_MAX));
        dp[0][0] = 0;
        vector<long long> sub(n+1, 0);
        for (int i = 0; i < n; ++i) {
            sub[i + 1] = sub[i] + nums[i];
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= min(k, i); ++j) {
                for (int m = 0; m < i; ++m) {
                    dp[i][j] = min(dp[i][j], max(dp[m][j-1],sub[i] - sub[m]));
                }
            }
        }
        return static_cast<int>(dp[n][k]);
    }
};

解释

它的目的是解决一个动态规划问题：将数组 nums 分割成 m 个连续子数组，使得这些子数组中各自元素的和的最大值最小化。函数返回这个最大值。

让我们逐步分析这个代码：

int splitArray(vector<int>& nums, int m) {

这是函数的签名，接受一个整数数组 nums 和一个整数 m，表示要将数组分割成的子数组的数量。

int n = nums.size();

得到数组 nums 的长度 n。

vector<vector<long long>> f(n + 1, vector<long long>(m + 1, LLONG_MAX));

初始化一个二维动态规划数组 f，大小为 (n+1) x (m+1)，所有元素初始值设为 LLONG_MAX，这表示最初的最大子数组和是非常大的，这是一种常见的初始化策略。

vector<long long> sub(n + 1, 0);

初始化一个累计和数组 sub，用于快速计算任意连续子数组的和。

for (int i = 0; i < n; i++) {
    sub[i + 1] = sub[i] + nums[i];
}

计算数组 nums 的累计和，存放在 sub 中，sub[i] 表示 nums 中前 i 个元素的和。

f[0][0] = 0;

初始化动态规划的基础情况：没有元素且不分割时，最大子数组和为 0。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= min(i, m); j++) {

这两层循环遍历所有的 i（考虑的元素数量）和 j（分割的子数组数量），注意 j 最多为 i 和 m 的较小者，因为不能有空的子数组。

for (int k = 0; k < i; k++) {

内部循环用于找到所有可能的前一个分割点 k。

f[i][j] = min(f[i][j], max(f[k][j - 1], sub[i] - sub[k]));

这是核心的状态转移方程。它尝试更新 f[i][j]，这是考虑前 i 个元素，分成 j 个子数组的最大子数组和的最小值。它在以下两个值之间取最小值：

• 当前的 f[i][j] 值。
• 最大子数组和的新候选值，这是由两部分组成的：
  • f[k][j - 1]：考虑前 k 个元素，分成 j-1 个子数组时的最大子数组和。
  • sub[i] - sub[k]：从第 k+1 个元素到第 i 个元素的子数组的和。

        }
    }
}

这三个大括号分别闭合内部循环、中间循环和外部循环。

return (int)f[n][m];

最后，函数返回分割点为 n（即整个数组）且分割数量为 m 的最大子数组和的最小值，由于 f 是 long long 类型，此处进行了类型转换为 int。

总的来说，这个动态规划解决方案非常巧妙地计算了在不同分割点的每种可能的分割方法中，最大的子数组和的最小值。