专栏首页眯眯眼猫头鹰的小树杈leetcode410. Split Array Largest Sum

leetcode410. Split Array Largest Sum

题目要求

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

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

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

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

将一个长度为n的正整数数组分割为m个非空的连续子数组,并分别计算每个子数组中所有元素的和。求一种分割方式,使得该分割方式生成的最大子数组和为所有分割方式中最小的。

比如题目中的例子nums = [7,2,5,10,8],m = 2 一共有四种分割方式:

  1. [7], [2,5,10,8]
  2. [7,2], [5,8,10]
  3. [7,2,5], [8,10]
  4. [7,2,5,8], [10]

其中第三种分割得到的最大子数组的和 是所有分割中最小的

思路一:动态规划

首先,我们可以通过递归的方式来遍历所有的分割方式,从而找到所有分割方式中最符合要求的那一种结果。代码如下:

    public int splitArray(int[] nums, int m) {
        //计算[0...i]中所有元素的和
        int[] sums = new int[nums.length+1];
        for(int i = 1 ; i<=nums.length ; i++) {
            sums[i] = nums[i-1] + sums[i-1];
        }
        return splitArray(nums, m, 0, sums);
    }
    
    //计算从cur位置开始,将其分割为m个子数组的最小分割场景
    public int splitArray(int[] nums, int m, int cur, int[] sums) {
        if(m == 1) {
            return sums[nums.length] - sums[cur];
        }
        int min = Integer.MAX_VALUE;
        int diff = Integer.MAX_VALUE;
        for(int i = cur+1 ; i<=nums.length-m+1 ; i++) {
            //当前元素为止,左边的子数组的元素和
            int left = sums[i]-sums[cur];
            //对右边的剩余元素递归的调用splitArray方法
            int right = splitArray(nums, m-1, i, sums);
            //如果出现二者之间的差递增的情况,则说明距离最优分割越来越远,则停止继续尝试
            if(diff < Math.abs(left - right)) {
                break;
            }
            diff = Math.abs(left - right);
            min = Math.min(min, Math.max(left, right));
        }
        return min;
    }

这种方法在大数据量的场景下会出现超时的问题,本质在于我们没有足够的复用中间的所有场景,如对于[i-j]这个子数组的k次分割的最优结果。如果我们记录从i到数组结尾进行k次分割的最优结果,该结果记录为dp[i][k],则从j到数组结尾进行k+1次分割的最优结果为min(max(num(j), dp[j+1][k]), max(nums(j)+num(j+1), dp[j+2][k])... ) 代码如下:

    public int splitArray(int[] nums, int m)
    {
        int L = nums.length;
        //记录0-i的元素和
        int[] S = new int[L+1];
        S[0]=0;
        for(int i=0; i<L; i++)
            S[i+1] = S[i]+nums[i];

        //如果m=1,则最小分割结果对应的是整个数组中所有元素的和
        int[] dp = new int[L];
        for(int i=0; i<L; i++)
            dp[i] = S[L]-S[i];

        for(int s=1; s<m; s++)
        {
            for(int i=0; i<L-s; i++)
            {
                dp[i]=Integer.MAX_VALUE;
                for(int j=i+1; j<=L-s; j++)
                {
                    int t = Math.max(dp[j], S[j]-S[i]);
                    if(t<=dp[i])
                        dp[i]=t;
                    else
                        break;
                }
            }
        }

        return dp[0];
    }

思路二:二分法

这是一个非常难想到的方法。二分法的难点一直在于如何划分初始边界,以及如何逐渐缩小边界并且确保左右指针可以相遇。在这里,边界被设置为该数组中可以得到的子数组元素和的最小值和最大值。 根据基本常识可知,数组的最大元素决定了该数组分割出的子数组的元素和的下界,而数组的元素和上界一定不会超过数组所有元素的和。 在确定了数组元素和的上界和下界之后, 就需要找出一种方法,来不断压缩区间直到最后一种。

可以使用中间位置作为数组元素和的边界,即假设所有的连续数组的和都不会超过mid值。假如按照这种方式得到的分割结果大于了规定的m个,则说明mid值作为最大元素和上界并不能够做到只分割出m个子数组,因此最大元素和上界一定在mid和有界中间。同理,假如按照这种方式得到的分割结果小于等于规定的m个,则说明mid值作为最大元素和上界能够满足分割出m个子数组,但是可能还存在更优解。通过这种二分法思路得到的最后结果就是所需要的最小分割结果。

    public int splitArray2(int[] nums, int m) {
        long sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0 ; i<nums.length ; i++) {
            max = Math.max(max, nums[i]);
            sum += nums[i];
        }
        if(m == 1) {
            return (int)sum;
        }
        long lft = max;
        long rgt = sum;
        while(lft <= rgt) {
            long mid = (lft + rgt) / 2;
            if(valid(nums, m, mid)) {
                rgt = mid - 1;
            }else {
                lft = mid + 1;
            }
        }
        return (int) lft;
        
    }
    
    public boolean valid(int[] nums, int m, long target) {
        int count = 1;
        long sum = 0;
        for(int i = 0 ; i<nums.length ; i++) {
            sum += nums[i];
            if(sum > target) {
                sum = nums[i];
                count++;
                if(count > m) {
                    return false;
                }
            }
        }
        return true;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode330. Patching Array

    假设有一个有序的正整数数组nums和一个整数n,最少添加几个元素到这个数组中,使得从1-n的所有整数都可以由这个数组中的值的或是几个值的和构成。

    眯眯眼的猫头鹰
  • leetcode525. Contiguous Array

    Given a binary array, find the maximum length of a contiguous subarray with equa...

    眯眯眼的猫头鹰
  • leetcode363. Max Sum of Rectangle No Larger Than K

    现有一个由整数构成的矩阵,问从中找到一个子矩阵,要求该子矩阵中各个元素的和为不超过k的最大值,问子矩阵中元素的和为多少? 注:后面的文章中将使用[左上角顶点坐标...

    眯眯眼的猫头鹰
  • LeetCode 26 Remove Duplicates from Sorted Array

    一份执着✘
  • LeetCode第一题

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    杨小杰
  • 让priority_queue支持小根堆的几种方法

    点击这里了解什么是priority_queue 前言 priority_queue默认是大根堆,也就是大的元素会放在前面 例如 ? #include<io...

    attack
  • Dimple在左耳听风ARTS打卡(第九期)

    所谓ARTS: 每周至少做一个LeetCode的算法题;阅读并点评至少一篇英文技术文章;学习至少一个技术技巧;分享一篇有观点和思考的技术文章。(也就是Algor...

    程序员小跃
  • LeetCode题组:第26题-删除排序数组中的重复项

    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。(注意这里提到了排序数组,也就是说数组是有序的。如果无序,...

    明天依旧可好
  • 第88场周赛

    第二反应:根据上述这个模拟超时过程,想一优化,shifts数组后面开始,逐个偏移,根据描述,后面的偏移会加到前面。于是有了后缀和这一说法。

    用户1145562
  • 十大经典排序算法整理汇总(附代码)

    本文整理并总结了十大经典的排序算法(冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、计数排序、基数排序、桶排序、堆排序)的时间复杂度、空间复杂度等性...

    godweiyang

扫码关注云+社区

领取腾讯云代金券