Java 中的拆分数组最大和

2025年3月17日 | 阅读 14 分钟

给定一个只包含非负整数的数组 numArr[] 和一个整数 sp。任务是将数组分割成 sp 个连续的子数组，使得这些子数组中最大的和最小化。注意，子数组永远不能为空。此问题的约束条件是输入数组 numArr[] 的大小不能超过 1000，且 sp 的最小值为 1。

例如，对于数组 numArr[] = {a1, a2, a3, a4, a5, a6} 和 sp = 2。那么，我们可以进行 5 种分割或划分方式。观察下图。

在每次划分中，我们都创建了两个子数组。假设在第一次划分中，g2（g2 中的元素）的和是 g1 和 g2 中最大的。同样，假设在第二次划分中 g4 的和是最大的，在第三次划分中 g6 的和是最大的，在第四次划分中 g8 的和是最大的，在第五次划分中 g10 的和是最大的。现在我们将找出（g2 的和、g4 的和、g6 的和、g8 的和、g10 的和）中的最小值。假设 g4 的和是最小的，那么我们就需要像第二次划分（如图所示）那样分割数组，g4 的和将是我们的答案。

示例 1

输入: numArr[] = [2, 7, 10, 5, 8, 9, 4], sp = 2

输出 24

解释: 让我们看看如何划分给定的输入数组。

划分 1: g1 = {2}, g2 = {7, 10, 5, 8, 9, 4}

g1 的和 = 2，g2 的和 = 43

（g1 的和, g2 的和）的最大值 = 43

划分 2: g1 = {2, 7}, g2 = {10, 5, 8, 9, 4}

g3 的和 = 9，g4 的和 = 36

（g3 的和, g4 的和）的最大值 = 36

划分 3: g1 = {2, 7, 10}, g2 = {5, 8, 9, 4}

g5 的和 = 19，g6 的和 = 26

（g5 的和, g6 的和）的最大值 = 26

划分 4: g1 = {2, 7, 10, 5}, g2 = {8, 9, 4}

g7 的和 = 24，g8 的和 = 21

（g7 的和, g8 的和）的最大值 = 24

划分 5: g1 = {2, 7, 10, 5, 8}, g2 = {9, 4}

g9 的和 = 32，g10 的和 = 13

（g9 的和, g10 的和）的最大值 = 32

划分 6: g1 = {2, 7, 10, 5, 8, 9}, g2 = {4}

g11 的和 = 41，g12 的和 = 4

（g11 的和, g12 的和）的最大值 = 41

现在，（43, 36, 26, 24, 32, 41）的最小值是 24。数字 24 来自划分 4。因此，我们需要使用划分 4 来获得子数组最大和的最小值。

示例 2

输入: numArr[] = [8, 3, 9, 2], sp = 4

输出 9

解释: 让我们看看如何划分给定的输入数组

划分: g1 = {8}, g2 = {3}, g3 = {9}, g4 = {2}。没有其他划分方式了。

在此划分中，（g1 的和、g2 的和、g3 的和、g4 的和）的最大值为 9。因此，我们的答案是 9。

示例 3

输入: numArr[] = [8, 3, 9, 2, 9, 6, 9, 0], sp = 10

输出: 无效输入

解释: numArr[] 中的元素总数为 8，sp 的值为 10。使用 8 个元素可以创建的最大子数组数为 8（每个子数组包含 1 个元素）。因此，如果我们尝试创建 10 个子数组（sp 的值为 10），那么至少有 2 个子数组必须为空。上面已经提到，从输入数组派生的子数组永远不能为空。因此，输入无效。

方法：使用动态规划

步骤 1: 方法是使用前缀和数组来计算元素的和。当遇到基准情况（只需要一个子数组时）时，需要计算剩余所有元素的和，这时我们需要 O(1) 时间内的答案。因此，第一步是填充 prefixSum[] 数组。

步骤 2: 从索引 currentIndex 为 0 和子数组数量 subArrCount 为 sp 开始。这表示范围 [0, size - 1] 内的子数组和 sp 个子数组。

步骤 3: 选择将构成当前子数组的元素，方法是从 currentIndex 开始遍历到 size - subArrCount 的索引。在每个索引

使用 prefixSum 计算当前子数组（fstSplitSum）中元素的和。
递归调用 getMinLargestSplitSum() 方法，以计算可以从剩余元素获得的最小最大子数组。
这两个值中的最大值构成了子数组和的最大值，前提是第一个子数组是 [currentIndex, i]。
对 j 从 0 到 size - subArrCount 的所有值重复此过程，然后将最小的可能 maxSplitSum 保存在与 currentIndex 和 subArrCount 对应的 memoization 表 memoArr[] 中。

返回 minLargestSplitSum 以避免重复计算，并将其保存在与 currentIndex 和 subArrCount 对应的 memoization 表 memoArr[] 中。

实施

观察基于上述算法实现的以下代码。

文件名: SplitArrLargestNum.java

public class SplitArrLargestNum
{
    // Defined as per the maximum array and the split count

    Integer memoArr[][];
    
    private int getMinLargestSplitSum(int prefixSum[], int currentIndex, int subArrCount) 
    {
        int size = prefixSum.length - 1;
        
        // The answer for the index currentIndex and the count of the subarray subArrCount is 
        // already computed. Hence, simply return the computed answer.
        if (memoArr[currentIndex][subArrCount] != null) 
        {
            return memoArr[currentIndex][subArrCount];
        }
        
        // Handling the Base Case
        // subarrayCount = 1 means there is single subarray and the rest of the elements must go 
        // in that subarray
        if (subArrCount == 1) 
        {
            return memoArr[currentIndex][subArrCount] = prefixSum[size] - prefixSum[currentIndex];
        }
        // Otherwise, use the recursive relation for finding the minimum largest sub array
        // sum from the currentIndex till the end of the array with subArrCount sub arrays that are left.
        int minLargestSplitSum = Integer.MAX_VALUE;
        for (int j = currentIndex; j <= size - subArrCount; j++) 
        {
            // keeping the sum of the first sub array.
            int fstSplitSum = prefixSum[j + 1] - prefixSum[currentIndex];            
            // computing the max sub array sum for the current 1st split.
            int maxSplitSum = Math.max(fstSplitSum, getMinLargestSplitSum(prefixSum, j + 1, subArrCount - 1));
            
            // computing the minimum sum from all of the combinations that are possible
            minLargestSplitSum = Math.min(minLargestSplitSum, maxSplitSum);
             
            // if the split sum is larger than the already computed answer then discard it 
            if (fstSplitSum >= minLargestSplitSum) 
            {
                break;
            }
        }
        return memoArr[currentIndex][subArrCount] = minLargestSplitSum;
    }
    
    public int partitionArray(int[] numArr, int sp) 
    {
        // Storing the prefix sum of array numArr
        int size = numArr.length;
        
        if(size < sp)
        {
            return -1;
        }        
        int prefixSum[] = new int[size + 1];
        for (int j = 0; j < size; j++) 
        {
            prefixSum[j + 1] = prefixSum[j] + numArr[j];
        }
        return getMinLargestSplitSum(prefixSum, 0, sp);
    }
    // main method
    public static void main(String argvs[])
    {
        // creating an object of the class SplitArrLargestNum
        SplitArrLargestNum obj = new SplitArrLargestNum();
        // input 1
        int numArr[] = {2, 7, 10, 5, 8, 9, 4};
        int size = numArr.length;
        int sp = 2;
        obj.memoArr = new Integer[size + 1][sp + 1];
        int ans = obj.partitionArray(numArr, sp);
        System.out.println("For the given array: ");
        for(int i = 0; i < size; i++)
        {
            System.out.print(numArr[i] +  " ");
        }
        System.out.println("");        
        if(ans == -1)
        {
            System.out.println("Parition for creating " + sp + " subarrays is not possible.");    
        }
        else
        {
            System.out.println("The minimum largest sum for the " + sp + " subarrays is: " + ans + ".");
        }
        System.out.println("\n");        
        // input 2
        int numArr1[] = {8, 3, 9, 2};
        size = numArr1.length;
        sp = 4;
        obj.memoArr = new Integer[size + 1][sp + 1];
        ans = obj.partitionArray(numArr1, sp);
        
        System.out.println("For the given array: ");
        
        for(int i = 0; i < size; i++)
        {
            System.out.print(numArr1[i] +  " ");
        }
        
        System.out.println("");
        
        if(ans == -1)
        {
            System.out.println("Parition for creating " + sp + " subarrays is not possible.");    
        }
        else
        {
            System.out.println("The minimum largest sum for the " + sp + " subarrays is: " + ans + ".");
        }
        
        System.out.println("\n");
        // input 3
        int numArr2[] = {8, 3, 9, 2, 9, 6, 9, 0};
        size = numArr2.length;
        sp = 10;
        
        obj.memoArr = new Integer[size + 1][sp + 1];
        ans = obj.partitionArray(numArr2, sp);
        
        System.out.println("For the given array: ");
        
        for(int i = 0; i < size; i++)
        {
            System.out.print(numArr2[i] +  " ");
        }
        
        System.out.println("");
        
        if(ans == -1)
        {
            System.out.println("Parition for creating " + sp + " subarrays is not possible.");    
        }
        else
        {
            System.out.println("The minimum largest sum for the " + sp + " subarrays is: " + ans + ".");
        }
        
        
    }
}

输出

For the given array: 
2 7 10 5 8 9 4 
The minimum largest sum for the 2 subarrays is: 24.


For the given array: 
8 3 9 2 
The minimum largest sum for the 4 subarrays is: 9.


For the given array: 
8 3 9 2 9 6 9 0 
Partition for creating 10 subarrays is not possible.

复杂度分析: 在上述程序中，我们通过递归覆盖了几乎 N * M 个状态。此外，我们使用了一个从 currentIndex 开始的 for 循环，这进一步增加了 O(N) 的时间复杂度。因此，程序的总时间复杂度为 O(N2 * M)，其中 N 表示输入数组中的总元素数，M 是允许的分割总数或子数组总数，也就是 sp。memoArr[] 数组占用的空间为 N * M。因此，程序的空间复杂度为 O(N * M)。

在上面的程序中，我们使用了递归来解决问题。然而，我们也可以仅使用循环来完成。观察以下程序。

文件名: SplitArrLargestNum1.java

public class SplitArrLargestNum1
{
// Defined as per the maximum array and the split count
// memoArr[p][q] means the minimum largest sum for the 
// array that starts from the index p and the splits that 
// are required from the index p is q
int memoArr[][];

public int partitionArray(int[] numArr, int sp) 
{
int size = numArr.length;

// if split is greater than the size of the input
// array then the given input is invalid
if(size < sp)
{
return -1;
}
// Storing the prefix sum of the numArr[] array
int[] prefixSum = new int[size + 1];
for (int j = 0; j < size; j++) 
{
prefixSum[j + 1] = prefixSum[j] + numArr[j];
}

for (int subArrCount = 1; subArrCount <= sp; subArrCount++) 
{
for (int currentIndex = 0; currentIndex < size; currentIndex++) 
{
// Handling the Base Case
// subarrayCount = 1 means there is single subarray and the rest of the elements must go 
// in that subarray
if (subArrCount == 1) 
{
memoArr[currentIndex][subArrCount] = prefixSum[size] - prefixSum[currentIndex];

continue;
}

// Otherwise, use the recursive relation for finding the minimum largest sub array
// sum from the currentIndex till the end of the array with subArrCount sub arrays that are left.
int minLargestSplitSum = Integer.MAX_VALUE;
for (int j = currentIndex; j <= size - subArrCount; j++) 
{
// Store the sum of the first subarray.
int fstSplitSum = prefixSum[j + 1] - prefixSum[currentIndex];

// Computing the maximum sub array sum for the current first split.
int largestSplitSum = Math.max(fstSplitSum, memoArr[j + 1][subArrCount - 1]);

// Computing the minimum from all of the combinations that are possible.
minLargestSplitSum = Math.min(minLargestSplitSum, largestSplitSum);

if (fstSplitSum >= minLargestSplitSum) 
{
break;
}
}

memoArr[currentIndex][subArrCount] = minLargestSplitSum;
}
}

return memoArr[0][sp];
}

// main method
public static void main(String argvs[])
{
// creating an object of the class SplitArrLargestNum1
SplitArrLargestNum1 obj = new SplitArrLargestNum1();


// input 1
int numArr[] = {2, 7, 10, 5, 8, 9, 4};
int size = numArr.length;
int sp = 2;
obj.memoArr = new int[size + 1][sp + 1];
int ans = obj.partitionArray(numArr, sp);

System.out.println("For the given array: ");

for(int i = 0; i < size; i++)
{
    System.out.print(numArr[i] +  " ");
}

System.out.println("");

if(ans == -1)
{
    System.out.println("Parition for creating " + sp + " subarrays is not possible.");    
}
else
{
    System.out.println("The minimum largest sum for the " + sp + " subarrays is: " + ans + ".");
}

System.out.println("\n");


// input 2
int numArr1[] = {8, 3, 9, 2};
size = numArr1.length;
sp = 4;

obj.memoArr = new int[size + 1][sp + 1];
ans = obj.partitionArray(numArr1, sp);

System.out.println("For the given array: ");

for(int i = 0; i < size; i++)
{
    System.out.print(numArr1[i] +  " ");
}

System.out.println("");

if(ans == -1)
{
    System.out.println("Parition for creating " + sp + " subarrays is not possible.");    
}
else
{
    System.out.println("The minimum largest sum for the " + sp + " subarrays is: " + ans + ".");
}

System.out.println("\n");

// input 3
int numArr2[] = {8, 3, 9, 2, 9, 6, 9, 0};
size = numArr2.length;
sp = 10;

obj.memoArr = new int[size + 1][sp + 1];
ans = obj.partitionArray(numArr2, sp);

System.out.println("For the given array: ");

for(int i = 0; i < size; i++)
{
    System.out.print(numArr2[i] +  " ");
}

System.out.println("");

if(ans == -1)
{
    System.out.println("Parition for creating " + sp + " subarrays is not possible.");    
}
else
{
    System.out.println("The minimum largest sum for the " + sp + " subarrays is: " + ans + ".");
}


}
}

输出

For the given array: 
2 7 10 5 8 9 4 
The minimum largest sum for the 2 subarrays is: 24.


For the given array: 
8 3 9 2 
The minimum largest sum for the 4 subarrays is: 9.


For the given array: 
8 3 9 2 9 6 9 0 
Partition for creating 10 subarrays is not possible.

复杂度分析: 上述程序的复杂度与前一个程序相同。

使用二分查找可以进一步降低程序的复杂度。

方法：使用二分搜索

步骤 1: 计算输入数组 numArr[] 中元素的和。将其存储在一个名为 sumArr 的变量中（也可以使用其他名称）。

步骤 2: 找出数组 numArr[] 中的最大元素。将其存储在一个变量中，在本例中为 maxEle。

步骤 3: 使用 maxEle 和 sumVar 固定二分查找的搜索空间，其中 maxEle 将作为左边界，sumArr 将作为右边界。

步骤 4: 使用循环开始二分查找，终止条件是：当左边界小于右边界时。

步骤 5: 找到中间值，并将其视为子数组允许的最大和。将其存储在一个变量中，即 maximumSumAllowed。

步骤 6: 计算和等于 maximumSumAllowed 的最小子数组数量。

步骤 7: 检查子数组的数量（在步骤 6 中找到）是否大于、小于或等于 sp。如果子数组的数量小于或等于 sp，则减小右边界的值，并将 maximumSumAllowed 的值赋给答案。如果子数组的数量大于 sp，则增加左边界的值。

步骤 8: 返回答案。

实施

让我们看看上述算法的实现。

文件名: SplitArrLargestNum2.java

public class SplitArrLargestNum2
{
    private int minSubArrReq(int[] numArr, int maximumSumAllowed) 
    {
        int size = numArr.length;
int currentSum = 0;
int splitsReq = 0;

for(int i = 0; i < size; i++)
{
if (currentSum + numArr[i] <= maximumSumAllowed) 
{
currentSum = currentSum + numArr[i];
} 
            
else 
{
// If the addition of the element makes the sum greater than the maximumSumAllowed
// then increase the number of splits required and reset the sum
currentSum = numArr[i];
splitsReq = splitsReq + 1;
}
}

return splitsReq + 1;
}
    
    public int partitionArray(int[] numArr, int sp) 
    {
        int size = numArr.length;
        
        // if split is greater than the size of the input
// array then the given input is invalid
if(size < sp)
{
return -1;
}
        // Computing the sum of all the elements and 
        // also finding the maximum element
        int sumArr = 0;
        int maxEle = Integer.MIN_VALUE;
        for (int j = 0; j < size; j++) 
        {
            sumArr = sumArr + numArr[j];
            maxEle = Math.max(maxEle, numArr[j]);
        }        
        // Defining the left and the right boundary of the binary search
        int lft = maxEle;
        int rgt = sumArr;
        int answer = 0;
        while (lft <= rgt) 
        {
            // computing the middle value
            int maximumSumAllowed = lft + (rgt - lft) / 2;
            
            // Computing the minimum number of splits. If the splits that are required are 
            // equal to or less than
            // sp move towards the left i.e., lesser values
            if (minSubArrReq(numArr, maximumSumAllowed) <= sp) 
            {
                rgt = maximumSumAllowed - 1;
                answer = maximumSumAllowed;
            } else 
            {
                // Moving towards the right if the required splits are more than sp
                lft = maximumSumAllowed + 1;
            }
        }        
        return answer;
    }
// main method
public static void main(String argvs[])
{
// creating an object of the class SplitArrLargestNum2
SplitArrLargestNum2 obj = new SplitArrLargestNum2();
// input 1
int numArr[] = {2, 7, 10, 5, 8, 9, 4};
int size = numArr.length;
int sp = 2;
//obj.memoArr = new int[size + 1][sp + 1];
int ans = obj.partitionArray(numArr, sp);

System.out.println("For the given array: ");

for(int i = 0; i < size; i++)
{
    System.out.print(numArr[i] +  " ");
}

System.out.println("");

if(ans == -1)
{
    System.out.println("Parition for creating " + sp + " subarrays is not possible.");    
}
else
{
    System.out.println("The minimum largest sum for the " + sp + " subarrays is: " + ans + ".");
}

System.out.println("\n");
// input 2
int numArr1[] = {8, 3, 9, 2};
size = numArr1.length;
sp = 4;
//obj.memoArr = new int[size + 1][sp + 1];
ans = obj.partitionArray(numArr1, sp);

System.out.println("For the given array: ");

for(int i = 0; i < size; i++)
{
    System.out.print(numArr1[i] +  " ");
}

System.out.println("");

if(ans == -1)
{
    System.out.println("Parition for creating " + sp + " subarrays is not possible.");    
}
else
{
    System.out.println("The minimum largest sum for the " + sp + " subarrays is: " + ans + ".");
}

System.out.println("\n");

// input 3
int numArr2[] = {8, 3, 9, 2, 9, 6, 9, 0};
size = numArr2.length;
sp = 10;

//obj.memoArr = new int[size + 1][sp + 1];
ans = obj.partitionArray(numArr2, sp);

System.out.println("For the given array: ");

for(int i = 0; i < size; i++)
{
    System.out.print(numArr2[i] +  " ");
}

System.out.println("");

if(ans == -1)
{
    System.out.println("Parition for creating " + sp + " subarrays is not possible.");    
}
else
{
    System.out.println("The minimum largest sum for the " + sp + " subarrays is: " + ans + ".");
}


}
}

输出

For the given array: 
2 7 10 5 8 9 4 
The minimum largest sum for the 2 subarrays is: 24.

For the given array: 
8 3 9 2 
The minimum largest sum for the 4 subarrays is: 9.

For the given array: 
8 3 9 2 9 6 9 0 
Partition for creating 10 subarrays is not possible.

复杂度分析: minSubArrReq() 方法使用一个循环，该循环遍历输入数组的每个元素。因此，时间复杂度为 O(n)。程序中使用的二分查找使用 O(log(s)) 的时间。因此，程序的总时间复杂度为 O(n * log(s))，其中 n 是数组中的总元素数，s 是数组中所有元素的总和。该程序不占用任何额外空间（未使用任何数据结构）。因此，空间复杂度是常数，即 O(1)。

下一个主题Java 中从双数组查找原始数组

Java 中的拆分数组最大和

示例 1

示例 2

示例 3

方法：使用动态规划

实施

方法：使用二分搜索

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

Java 中的拆分数组最大和

示例 1

示例 2

示例 3

方法：使用动态规划

实施

方法：使用二分搜索

实施

相关帖子

Java Program to Display Even Numbers From 1 to 100

计算二叉树奇数层和偶数层节点和之差的 Java 程序

Java 判断单链表是否为回文的程序

将二叉树转换为二叉搜索树的 Java 程序

如何在 Java 中将 double 转换为 int

打印以下图案的 Java 程序 5

Java 中的交错字符串问题

Java Program to Display Odd Numbers From 1 to 100

如何在 Java 中将二进制转换为十进制

如何在 Java 中将 int 转换为 long

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器