分割数组的最大值

分割数组的最大值，将一个数组分割成n个连续的子数组，使每个子数组的最大值最小。

题目

在m个节点的分布式计算系统中，有一批任务需要执行，每个任务需要的时间式array[i]，每个节点同一时间只能执行一个任务，每个节点只能执行连续的任务，例如i，i+1，i+2，但是不能执行i，i+2。请问任务完成的最短时间
输入
输入数据包含两行
第一行，空格分割的两个整数m和n，分布表示节点个数和任务个数(m>0,n>=0)
第二行，空格分割的正整数序列，表示每个任务需要的时间
输出
一个整数，表示最短完成时间
样例输入
3 5
1 5 3 4 2
样例输入
6
提示
第一个节点执行：任务1和任务2，耗时=1+5=6
第二个节点执行：任务3，耗时=3
第三个节点执行：任务4和任务5，耗时=2+4=6

思路

将一个数组分割成n个连续的子数组，使每个子数组的最大值最小。（同leecode 410）

解法一、 二分法

1.给出一个完成任务的时间x，然后将任务分成每个子节点任务时间<=x，如果完成任务需要的节点数<=给出的节点数，那么满足条件。用来判断是否满足条件的过程可以用暴力方法求解。
2.给出时间x可以从完成任务的平均时间开始不断+1，找到第一个满足条件的x，就是完成任务最短时间。或者使用二分法 sum/m<=x<=sum，不断二分计算中间值，可以减少时间复杂度。
源码

import java.util.Scanner;

public class test3 {
	public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int nodeNum=sc.nextInt();
        int taskNum=sc.nextInt();
        int time[] = new int[taskNum];
        int sum=0;
        for(int i=0;i<taskNum;i++)
        {
        	time[i]=sc.nextInt();
        } 
        System.out.println(splitArray(time,nodeNum));
    }
	//二分法划分，每次给出一个时长x，判断是否满足条件
	public static int splitArray(int[] nums, int m) {
		int sum=0;
		for(int i=0;i<nums.length;i++)
        {
        	sum+=nums[i];
        } 
		int low=sum/m;
		int high=sum;
		int result=low;
		while(low<=high)
		{
			int mid=(low+high)/2;
			if(isFit(nums,mid,m))
			{
				if(isFit(nums,low,m)) {
					result=low;
					break;
				}
				else
				{
					low+=1;
					high=mid;
				}
			}
			else
			{
				low=mid+1;
			}			
		}
        for(int i=0;i<nums.length;i++)
        {
        	if(result<nums[i])
        		result=nums[i];
        } 
        return result;
    }

	//暴力求解当前时长是否满足条件
	private static Boolean isFit(int time[],int maxsumtime,int nodeNum)
	{
		int count=0,sum=0;
		for(int i=0;i<time.length;i++)
		{
			sum+=time[i];
			if(i+1<time.length-1)
			{
				if(sum<=maxsumtime&&(sum+time[i+1])>maxsumtime)
				{
					count++;
					sum=0;
				}			
			}
			else {
				if(sum<=maxsumtime&&(sum+time[i+1])>maxsumtime)
				{
					count=count+2;
				}
				else
				{
					count+=1;
				}
				break;
			}
		}
		System.out.print("count:"+count);
		System.out.println(" maxsumtime:"+maxsumtime);
		if(count>nodeNum)
			return false;
		return true;
	}
}

结果
第一行是使用二分的结果，第二行是顺序查找的结果

解法二、 动态规划

这是一类最大最小问题。
简单说就是将数组划分为多组，每组会求一个和，多组的和最大值的可能性很多，求多组和的最小值的可能性。
状态定义：f[i][j]表示nums[0] ~ nums[j]共j+1个元素划分为i组的和的最大最小值。
可初始化的状态：f[1][j]表示nums[0]~nums[j]划分为1组的分组和的最大最小值，显然f[1][j] = sum(0, j)，包含边界。
状态迁移方程：f[i][j] = min(max(f[i-1][k], sum(k+1, j))), 0<= k < j
这种问题的状态迁移方程很具有代表性，即在右边划一段出来，先把问题规模-1，然后剩下的只需要再切分为i-1组即可。
其中k是这缩小问题规模的切分点。

源码

public class dp {
	public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int nodeNum=sc.nextInt();
        int taskNum=sc.nextInt();
        int time[] = new int[taskNum];
        for(int i=0;i<taskNum;i++)
        {
        	time[i]=sc.nextInt();
        } 
        System.out.println(dp(time,nodeNum));
    }
	public static int dp(int time[],int nodeNum)
	{
		int f[][]=new int[nodeNum+1][time.length] ;
		int presum[]=new int[time.length];
		for(int i=2;i<nodeNum+1;i++)
		{
			for(int j=0;j<time.length;j++)
			{
				f[i][j]=2147483647;
			}
		}
		f[1][0]=time[0];
		presum[0]=time[0];
		for(int i=1;i<time.length;i++)
		{
			presum[i]=presum[i-1]+time[i];
			f[1][i]=presum[i];
		}
		for(int i=2;i<nodeNum+1;i++)
		{
			for(int j=i-1;j<time.length;j++)
			{
				for(int k=0;k<j;k++)
				{
					f[i][j]=Math.min(f[i][j], Math.max(f[i-1][k], presum[j]-presum[k]));
				}
			}
		}
		return f[nodeNum][time.length-1];
	}
}

结果