使用 oh-my-zsh

410、分割数组的最大值

给定一个非负整数数组和一个整数 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，在所有情况中最小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-array-largest-sum

题解

1、暴力法

枚举所有的可能组合，去最优。深度优先遍历。

• 代码

// java

class Solution {
    private int ans;
    private int n, m;
    // i 当前的下标
    // cntSubarrays 子集数量
    // curSum 当前和
    // curMax 当前和的最大值
    private void dfs(int[] nums, int i, int cntSubarrays, int curSum, int curMax) {
        if (i == n && cntSubarrays == m) {
            ans = Math.min(ans, curMax);
            return;
        }
        if (i == n) {
            return;
        }
        if (i > 0) {
            
            dfs(nums, i + 1, cntSubarrays, curSum + nums[i], Math.max(curMax, curSum + nums[i]));
        }
        if (cntSubarrays < m) {
            dfs(nums, i + 1, cntSubarrays + 1, nums[i], Math.max(curMax, nums[i]));
        }
    }
    public int splitArray(int[] nums, int M) {
        ans = Integer.MAX_VALUE;
        n = nums.length;
        m = M;
        dfs(nums, 0, 0, 0, 0);
        return ans;
    }
}

// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/split-array-largest-sum/solution/fen-ge-shu-zu-de-zui-da-zhi-by-leetcode/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2、动态规划

$dp[i][j] 指将nums[0…i]分成j份时，分割子数组最大和的最小值$

• 代码

// java

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[][] f = new int[n + 1][m + 1];
        int[] sub = new int[n + 1];
        // 数组初始化
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = Integer.MAX_VALUE;
            }
        }
        // 前缀和
        for (int i = 0; i < n; i++) {
            sub[i + 1] = sub[i] + nums[i];
        }
        f[0][0] = 0;
        // 数组
        for (int i = 1; i <= n; i++) {
            // 遍历每组的数字
            for (int j = 1; j <= m; j++) {
                // 求f[i][j]的最小值
                for (int k = 0; k < i; k++) {
                    // 根据之前求得的更新当前目标值
                    f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));
                }
            }
        }
        return f[n][m];        
    }
}

// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/split-array-largest-sum/solution/fen-ge-shu-zu-de-zui-da-zhi-by-leetcode/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3、二分搜索+贪心

二分搜索 解决查找最优的可能子集

贪心 求子集的和

• 代码

// java
class Solution {
    public int splitArray(int[] nums, int m) {
        long l = 0;
        long r = 0;        
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            r += nums[i];// 求数组的总和
            if (l < nums[i]) {
                l = nums[i];// 求最大值
            }
        }
        long ans = r;
        while (l <= r) {
            // 目标的子集和
            long mid = (l + r) >> 1;
            long sum = 0;
            int cnt = 1;
            // 以mid作为子集大小的限制，求可划分的子集数量
            for (int i = 0; i < n; i++) {
                // 子集和太大
                if (sum + nums[i] > mid) {
                    cnt ++;
                    sum = nums[i];// 重置子集和
                } else {// 子集和太小，继续累加
                    sum += nums[i];
                }
            }
            // 二分
            if (cnt <= m) {// 分割子数组数量少了 或者刚好
                // 更新最小的子集最大和
                ans = Math.min(ans, mid);
                r = mid - 1;
            } else {// // 分割子数组数量多了
                l = mid + 1;
            }
        }
        return (int)ans;      
    }
}

// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/split-array-largest-sum/solution/fen-ge-shu-zu-de-zui-da-zhi-by-leetcode/

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com