410. 分割数组的最大值 二分法

410. 分割数组的最大值

难度：困难
2020/7/25每日一题打卡
题目描述

解题思路

1、二分法

参考题解：二分查找 + 贪心（Java）

大于的时候舍弃，小于的时候保留，这样左右向中间逼近的过程中能得到M的最小值

很多二分查找，找边界值都是用这种思想
二分的左边界是数组最大值，因为当m = n的时候，此时最小就是这个最大值。
右边界是数组里所有数字的和，当m = 1的时候，就是把整个数组作为一个完整的划分，此时最大值就是数组数字的和。

从整体上来看，是在左边界和右边界里找一个合适的值，使得得到的m刚好满足题目要求，mid值越大，m越小，是个单调不增函数

按这种思路可以写出代码

 /*
		     * 410. 分割数组的最大值
		     * 难度：困难
		     * 二分法加贪心
		     */
		    public int splitArray(int[] nums, int m) {
		    	
		    	int left = 0,right = 0;  //left是整个数组里的最大值，sum是整个数组里数字的和
		    	for (int i = 0; i < nums.length; i++) {
					left = nums[i]>left?nums[i]:left;
					right += nums[i];
					
				}
		    	while(left < right) {
		    		int mid = left + (right - left)/2;
		    		int count = 1,temp = 0;;
		    		for (int i = 0; i < nums.length; i++) {
						if(temp + nums[i] > mid) {  //这里用贪心思想，尽可能把更多的数字分到一个划分里
							temp = 0;
							count++;
						}
						temp += nums[i];
					}
		    		if(count > m) { //如果划分出来的子数组太多了，说明mid值取得太小
		    			left = mid + 1;
		    		}else {  //如果划分出的子数组少了，说明mid值太大了
		    			right = mid;
		    			
		    		}
		    		//System.out.println(mid+" "+count);
		    	}
		    	
		    	return  left;

		    }

2、动态规划法

没看懂，不理解，先抄着，三层循环

//动态规划法
		    //dp[i][j]表示将数组的前 i个数分割为 j 段所能得到的最大连续子数组和的最小值
		    public int splitArray1(int[] nums, int m) {
		    	int n = nums.length;
		    	int[][] dp = new int[n+1][m+1];
		    	for (int i = 0; i <= n; i++) {
		            Arrays.fill(dp[i], Integer.MAX_VALUE);
		        }
		    	int[] sum = new int[n+1];
		    	for (int i = 1; i < sum.length; i++) {
					sum[i] = sum[i-1] + nums[i-1];
				}
		    	dp[0][0] = 0;
		    	for (int i = 1; i <= n; i++) {   //枚举区间的末尾
					for (int j = 1; j <= Math.min(i, m); j++) {  //枚举拆分子区间的个数
						for (int k = j; k <= i; k++) {
							dp[i][j] = Math.min(dp[i][j], Math.max(dp[k-1][j-1],sum[i]-sum[k-1]));
						}
						
					}
				}
		    	return dp[n][m];

		    }