小旭讲解 LeetCode 410. 分割数组的最大值

B站视频源

原题

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

示例:

输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

思路 – 动态规划

dp[i][j] 代表前 i 个元素，分成 j 组的情况下，全局最优值为 dp[i][j]

代码

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        // 重叠子问题 最优子结构
        // dp[i][j] 将其前 i 个元素分成 j 组，全局最小值
        // 7 2 5 10 8
        //          i dp[i][1] = sum[i]
        //   k      i 从 1 到 k 分成 j - 1，从 k + 1到 i 分成一组
        // dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sum[i] - sum[k]));
        int n = nums.size();
        long long dp[n + 5][55], sum[n + 5];
        memset(dp, 0x3f, sizeof dp);
        memset(sum, 0, sizeof sum);
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + nums[i - 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= min(i, m); ++j) {
                if (j == 1) {
                    dp[i][j] = sum[i];
                } else {
                    for (int k = 1; k <= i - 1; ++k) {
                        dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sum[i] - sum[k]));
                    }
                }
            }
        }
        return dp[n][m];
    }
};

复杂度分析

时间复杂度：O(n^2 * m) n 为数组长度，m 为分组个数
空间复杂度：O(n^2)

思路 – 二分搜索

找到目标值（全局最小值）的二段性，在目标值范围内进行二分搜索。

代码

class Solution {
public:
    bool check(vector<int>& nums, int m, int target) {
        long long cnt = 1, sum = 0 ;
        for (int i = 0; i < nums.size(); ++i) {
            if (sum + nums[i] > target) {
                sum = nums[i];
                ++cnt;
            } else {
                sum += nums[i];
            }
        }
        return cnt <= m;
    }
    int splitArray(vector<int>& nums, int m) {
        // m = 2
        // value: 7 2 5 10 8
        // index: 1 2 3 4  5
        // min: 10, max: 32
        // 10, 11, 12, 13, ..... 17, 18, 19, 20, ..... 32
        // -----不可行--------------，---------可行--------
        long long  l = 0, r = 0, mid;
        for (auto n : nums) {
            if (l < n) l = n;
            r += n;
        }
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(nums, m, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

复杂度分析

时间复杂度：O(n * logk) n 为数组的长度，k 为 10^{12}
空间复杂度：O(1)

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/split-array-largest-sum/

本文为原创文章，欢迎分享，勿全文转载，如果内容你实在喜欢，可以加入收藏夹，说不定哪天故事又继续更新了呢。
本文地址：https://qoogle.top/xiaoxu-tutorial-leetcode-410-split-array-largest-sum/