410. 分割数组的最大值 - [困难]- (二分+贪心)

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

二分+贪心

• 想到了子序列的和最大值是整个数组的和，这个作为二分的上界
• 没想到元素的最大值作为二分的下届
• 想到了可以不断的从左到右以元素累加的形式找最大值，且想到类似猜数的形式，猜一个最大值，不断探索，但是没想到具体实现代码思路
• 个人总结
  • 二分标准模板思维已经很熟悉，也想到了猜数的经典套路
  • 但是把问题抽象成这种经典套路的能力还是不行，还需要多练习，持续循环的总结

package com.company.binarySearch;

public class Solution10 {

    public int splitArray(int[] nums, int m) {
        // left 单个元素得最大值，right所有元素得和
        int left = 0, right = 0;
        for (int i = 0; i < nums.length; i++) {
            right += nums[i];
            if (left < nums[i]) {
                left = nums[i];
            }
        }

        while (left < right) {
            int mid = (right - left) / 2 + left;

            if (check(nums, mid, m)) {
                //以mid最为最大值，满足条件的拆分子序列数量 小于目标个数m，则说明mid最为最大值太大了拆分的个数不够m个序列，因此right左移动的目的是缩小最大值
                //以mid最为最大值，满足条件的拆分子序列数量 等于目标个数m,只能说明找到了一种满足条件的拆分方式，但是还没找到子序列最大值最小的情况，为了找到让这个值更小所有此right左移动的目的是缩小最大值
                right = mid;

            } else {
                //调大最大值
                left = mid + 1;
            }
        }
        return left;
    }

    // max 已经假设是这一轮的最大值，所有其它拆分子序列的和必须小于max,当拆分子序列的和大于max的时候开始另外一个拆分
    public boolean check(int[] nums, int max, int m) {
        //拆分子序列的和
        int sum = 0;

        //拆分子序列的个数
        int cnt = 1;

        for (int i = 0; i < nums.length; i++) {
            if (sum + nums[i] > max) {
                cnt++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }

        //满足条件的拆分子序列数量 小于等于目标个数m
        return cnt <= m;
    }
}

基本上能有贪心的问题就能用动态规划 

专项练习动态规划的时候再来做这个

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(f[i], Integer.MAX_VALUE);
        }
        int[] sub = new int[n + 1];
        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 <= Math.min(i, m); 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];
    }
}