LeetCode 410 Split Array Largest Sum

Tag: 二分搜索 动态规划 LeetCode Posted on 2022-02-03 18:01:23 Edited on 2022-02-05 16:55:53 Views: 175

题目分析

https://leetcode.com/problems/split-array-largest-sum/

注意是非空的连续子数组。

暴力遍历法 / 递归法 / 动态规划法

时间复杂度 O(mn)

class Solution {
public:
    vector<vector<int>> cache;
    int splitArray(vector<int>& nums, int m) {
        vector<vector<int>> cache(m + 1, vector<int>(nums.size() + 1, -1));
        this->cache = cache;
        return helper(nums, m, 0);
    }
    
    int helper(vector<int>& nums, int m, int s) {
        if (m == 1) {
            int ans = 0;
            for (int i = s; i < nums.size(); i++) {
                ans += nums[i];
            }
            return ans;
        }
        if (cache[m][s] != -1) return cache[m][s];
        
        int ans = INT_MAX;
        int c = 0;
        for (int i = s; m - 1 <= nums.size() - 1 - i; i++) {
            c += nums[i];
            ans = min(ans, max(c, helper(nums, m - 1, i + 1)));
        }
        cache[m][s] = ans;
        return ans;
    }
};

二分搜素

https://labuladong.gitee.io/algo/2/21/63/

这题似乎可以理解成leetcode 1011 的换皮,逻辑是一模一样的。 D天对应本题分割数组的数量m;按顺序装运对于本题的连续数组; 求最小运载能力即本题的求各数组和的最大值的最小值

题目让求的是将数组分为 m 个子数组时的最小最大子数组和, 反向思考,我们可以求最小的最大子数组和,其满足可以 m 分数组。

最后的代码与 LeetCode 1011 一模一样。

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int l = *max_element(nums.begin(), nums.end());
        int r = accumulate(nums.begin(), nums.end(), 0);
        while (l <= r) {
            int t = l + (r - l) / 2;
            if (isOkay(nums, m, t)) {
                r = t - 1;
            } else {
                l = t + 1;
            }
        }
        return l;
    }
    
    bool isOkay(vector<int>& nums, int m, int x) {
        int count = 1;
        int rest = x;
        for (int i = 0; i < nums.size(); i++) {
            if (rest >= nums[i]) {
                rest -= nums[i];
            } else {
                count++;
                rest = x - nums[i];
            }
        }
        return count <= m;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/