频道栏目
首页 > 考试 > 其他 > 正文
【Leetcode】410. Split Array Largest Sum
2017-01-01 09:55:00         来源:举头天外望,无我这般人  
收藏   我要投稿

【Leetcode】410. 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:Given m satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.

思路:

先计算subarrays sum的上下界,在该范围内二分法搜索满足条件的sum(以该sum贪心划分array 看能否满足sum>=所有subarray的sum)。并记录最小的sum。

本次contest只做出来这三题。\

 

算法:

 

   public int splitArray(int[] nums, int m) {
        int high = 0, low = 0, mid = 0, ans = 0;
        for (int num : nums) {
            high += num;
            low = Math.max(num, low);
        }

        if (m == 1)
            return high;
        if (m == nums.length)
            return low;
        ans = high;
        while (low <= high) {
            mid = low + (high - low) / 2;

            boolean flag = true;
            int sum = nums[0];
            int count = 1;
            for (int i = 1; i < nums.length; i++) {
                sum += nums[i];
                if (sum > mid) {
                    count++;
                    sum = nums[i];
                }
                if (count > m) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                high = mid - 1;
                ans = mid;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }
点击复制链接 与好友分享!回本站首页
上一篇:HDU 5833
下一篇:【Leetcode】409. Longest Palindrome
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站