小旭讲解 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/

小旭讲解 LeetCode 410. 分割数组的最大值leetcode刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小旭讲解 LeetCode 410. 分割数组的最大值leetcode刷题题解