Dado un Array[] de N elementos y un número K. ( 1 <= K <= N ) . Divida la array dada en K subarreglos (deben cubrir todos los elementos). La suma máxima de subarreglos que se puede lograr de los K subarreglos formados debe ser la mínima posible. Encuentre esa posible suma de subarreglo.
Ejemplos:
Entrada: Array[] = {1, 2, 3, 4}, K = 3
Salida: 4
La división óptima es {1, 2}, {3}, {4}. La suma máxima de todos los subarreglos es 4, que es el mínimo posible para 3 divisiones.
Entrada: Array[] = {1, 1, 2} K = 2
Salida: 2
Enfoque ingenuo:
- La idea es averiguar todas las posibilidades.
- Para averiguar todas las posibilidades utilizamos BACKTRACKING .
- En cada paso, dividimos la array en sub-array y encontramos la suma de la sub-array y actualizamos la suma máxima
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
int ans = 100000000;
// the answer is stored in ans
// we call this function solve
void solve(int a[], int n, int k, int index, int sum,
int maxsum)
{
// K=1 is the base Case
if (k == 1) {
maxsum = max(maxsum, sum);
sum = 0;
for (int i = index; i < n; i++) {
sum += a[i];
}
// we update maxsum
maxsum = max(maxsum, sum);
// the answer is stored in ans
ans = min(ans, maxsum);
return;
}
sum = 0;
// using for loop to divide the array into K-subarray
for (int i = index; i < n; i++) {
sum += a[i];
// for each subarray we calculate sum ans update
// maxsum
maxsum = max(maxsum, sum);
// calling function again
solve(a, n, k - 1, i + 1, sum, maxsum);
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int k = 3; // K divisions
int n = 4; // Size of Array
solve(arr, n, k, 0, 0, 0);
cout << ans << "\n";
}
C
#include <stdio.h>
int ans = 100000000;
// the answer is stored in ans
// we call this function solve
// max function is used to find max of two elements
int max(int a, int b) { return a > b ? a : b; }
// min function is used to find min of two elements
int min(int a, int b) { return a < b ? a : b; }
void solve(int a[], int n, int k, int index, int sum,
int maxsum)
{
// K=1 is the base Case
if (k == 1) {
maxsum = max(maxsum, sum);
sum = 0;
for (int i = index; i < n; i++) {
sum += a[i];
}
// we update maxsum
maxsum = max(maxsum, sum);
// the answer is stored in ans
ans = min(ans, maxsum);
return;
}
sum = 0;
// using for loop to divide the array into K-subarray
for (int i = index; i < n; i++) {
sum += a[i];
// for each subarray we calculate sum ans update
// maxsum
maxsum = max(maxsum, sum);
// calling function again
solve(a, n, k - 1, i + 1, sum, maxsum);
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int k = 3; // K divisions
int n = 4; // Size of Array
solve(arr, n, k, 0, 0, 0);
printf("%d", ans);
}
Java
class GFG {
public static int ans = 10000000;
public static void solve(int a[], int n, int k,
int index, int sum, int maxsum)
{
// K=1 is the base Case
if (k == 1) {
maxsum = Math.max(maxsum, sum);
sum = 0;
for (int i = index; i < n; i++) {
sum += a[i];
}
// we update maxsum
maxsum = Math.max(maxsum, sum);
// the answer is stored in ans
ans = Math.min(ans, maxsum);
return;
}
sum = 0;
// using for loop to divide the array into
// K-subarray
for (int i = index; i < n; i++) {
sum += a[i];
// for each subarray we calculate sum ans update
// maxsum
maxsum = Math.max(maxsum, sum);
// calling function again
solve(a, n, k - 1, i + 1, sum, maxsum);
}
}
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4 };
int k = 3; // K divisions
int n = 4; // Size of Array
solve(arr, n, k, 0, 0, 0);
System.out.println(ans + "\n");
}
}
Python3
ans = 10000000 def solve(a, n, k, index, sum, maxsum): global ans # K=1 is the base Case if (k == 1): maxsum = max(maxsum, sum) sum = 0 for i in range(index,n): sum += a[i] # we update maxsum maxsum = max(maxsum, sum) # the answer is stored in ans ans = min(ans, maxsum) return sum = 0 # using for loop to divide the array into # K-subarray for i in range(index, n): sum += a[i] # for each subarray we calculate sum ans update # maxsum maxsum = max(maxsum, sum) # calling function again solve(a, n, k - 1, i + 1, sum, maxsum) # driver code arr = [ 1, 2, 3, 4 ] k = 3 # K divisions n = 4 # Size of Array solve(arr, n, k, 0, 0, 0) print(ans) # this code is contributed by shinjanpatra
C#
using System;
class GFG {
public static int ans = 10000000;
public static void solve(int []a, int n, int k,
int index, int sum, int maxsum)
{
// K=1 is the base Case
if (k == 1) {
maxsum = Math.Max(maxsum, sum);
sum = 0;
for (int i = index; i < n; i++) {
sum += a[i];
}
// we update maxsum
maxsum = Math.Max(maxsum, sum);
// the answer is stored in ans
ans = Math.Min(ans, maxsum);
return;
}
sum = 0;
// using for loop to divide the array into
// K-subarray
for (int i = index; i < n; i++) {
sum += a[i];
// for each subarray we calculate sum ans update
// maxsum
maxsum = Math.Max(maxsum, sum);
// calling function again
solve(a, n, k - 1, i + 1, sum, maxsum);
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4 };
int k = 3; // K divisions
int n = 4; // Size of Array
solve(arr, n, k, 0, 0, 0);
Console.Write(ans + "\n");
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
var ans = 10000000;
function solve(a, n, k, index, sum, maxsum)
{
// K=1 is the base Case
if (k == 1) {
maxsum = Math.max(maxsum, sum);
sum = 0;
for (var i = index; i < n; i++) {
sum += a[i];
}
// we update maxsum
maxsum = Math.max(maxsum, sum);
// the answer is stored in ans
ans = Math.min(ans, maxsum);
return;
}
sum = 0;
// using for loop to divide the array into
// K-subarray
for (var i = index; i < n; i++) {
sum += a[i];
// for each subarray we calculate sum ans update
// maxsum
maxsum = Math.max(maxsum, sum);
// calling function again
solve(a, n, k - 1, i + 1, sum, maxsum);
}
}
var arr = [ 1, 2, 3, 4 ];
var k = 3; // K divisions
var n = 4; // Size of Array
solve(arr, n, k, 0, 0, 0);
document.write(ans + "\n");
// this code is contributed by shivanisinghss2110
</script>
Producción
4
Complejidad de tiempo : O((N−1)c(K−1) ( NOTA: ‘c’ aquí representa combinaciones, es decir ((n-1)!/((nk)!*(k-1)!)
Donde N es el número de elementos del arreglo y K es el número de divisiones.
Enfoque eficiente:
- La idea es utilizar la búsqueda binaria para encontrar una solución óptima.
- Para la búsqueda binaria, la suma mínima puede ser 1 y la suma máxima puede ser la suma de todos los elementos.
- Para verificar si mid es la suma máxima de subarreglo posible. Mantenga un conteo de subarreglos, incluya todos los elementos posibles en el subarreglo hasta que su suma sea menor que la mitad. Después de esta evaluación, si el conteo es menor o igual a K, entonces se puede lograr la mitad, de lo contrario no. (Dado que si el recuento es menor que K, podemos dividir aún más cualquier subarreglo, su suma nunca aumentará mid).
- Encuentre el valor mínimo posible de mid que satisfaga la condición.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if mid can
// be maximum sub - arrays sum
bool check(int mid, int array[], int n, int K)
{
int count = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
// If individual element is greater
// maximum possible sum
if (array[i] > mid)
return false;
// Increase sum of current sub - array
sum += array[i];
// If the sum is greater than
// mid increase count
if (sum > mid) {
count++;
sum = array[i];
}
}
count++;
// Check condition
if (count <= K)
return true;
return false;
}
// Function to find maximum subarray sum
// which is minimum
int solve(int array[], int n, int K)
{
int* max = max_element(array, array + n);
int start = *max; //Max subarray sum, considering subarray of length 1
int end = 0;
for (int i = 0; i < n; i++) {
end += array[i]; //Max subarray sum, considering subarray of length n
}
// Answer stores possible
// maximum sub array sum
int answer = 0;
while (start <= end) {
int mid = (start + end) / 2;
// If mid is possible solution
// Put answer = mid;
if (check(mid, array, n, K)) {
answer = mid;
end = mid - 1;
}
else {
start = mid + 1;
}
}
return answer;
}
// Driver Code
int main()
{
int array[] = { 1, 2, 3, 4 };
int n = sizeof(array) / sizeof(array[0]);
int K = 3;
cout << solve(array, n, K);
}
Java
// Java implementation of the above approach
class GFG {
// Function to check if mid can
// be maximum sub - arrays sum
static boolean check(int mid, int array[], int n, int K)
{
int count = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
// If individual element is greater
// maximum possible sum
if (array[i] > mid)
return false;
// Increase sum of current sub - array
sum += array[i];
// If the sum is greater than
// mid increase count
if (sum > mid) {
count++;
sum = array[i];
}
}
count++;
// Check condition
if (count <= K)
return true;
return false;
}
// Function to find maximum subarray sum
// which is minimum
static int solve(int array[], int n, int K)
{
int start = 1;
for (int i = 0; i < n; ++i) {
if (array[i] > start)
start = array[i]; //Max subarray sum, considering subarray of length 1
}
int end = 0;
for (int i = 0; i < n; i++) {
end += array[i]; //Max subarray sum, considering subarray of length n
}
// Answer stores possible
// maximum sub array sum
int answer = 0;
while (start <= end) {
int mid = (start + end) / 2;
// If mid is possible solution
// Put answer = mid;
if (check(mid, array, n, K)) {
answer = mid;
end = mid - 1;
}
else {
start = mid + 1;
}
}
return answer;
}
// Driver Code
public static void main(String[] args)
{
int array[] = { 1, 2, 3, 4 };
int n = array.length;
int K = 3;
System.out.println(solve(array, n, K));
}
}
// This code is contributed by AnkitRai01
Python3
# Python 3 implementation of the above approach # Function to check if mid can # be maximum sub - arrays sum def check(mid, array, n, K): count = 0 sum = 0 for i in range(n): # If individual element is greater # maximum possible sum if (array[i] > mid): return False # Increase sum of current sub - array sum += array[i] # If the sum is greater than # mid increase count if (sum > mid): count += 1 sum = array[i] count += 1 # Check condition if (count <= K): return True return False # Function to find maximum subarray sum # which is minimum def solve(array, n, K): start = max(array) #Max subarray sum, considering subarray of length 1 end = 0 for i in range(n): end += array[i] #Max subarray sum, considering subarray of length n # Answer stores possible # maximum sub array sum answer = 0 while (start <= end): mid = (start + end) // 2 # If mid is possible solution # Put answer = mid; if (check(mid, array, n, K)): answer = mid end = mid - 1 else: start = mid + 1 return answer # Driver Code if __name__ == '__main__': array = [1, 2, 3, 4] n = len(array) K = 3 print(solve(array, n, K)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to check if mid can
// be maximum sub - arrays sum
static Boolean check(int mid, int []array,
int n, int K)
{
int count = 0;
int sum = 0;
for (int i = 0; i < n; i++)
{
// If individual element is greater
// maximum possible sum
if (array[i] > mid)
return false;
// Increase sum of current sub - array
sum += array[i];
// If the sum is greater than
// mid increase count
if (sum > mid)
{
count++;
sum = array[i];
}
}
count++;
// Check condition
if (count <= K)
return true;
return false;
}
// Function to find maximum subarray sum
// which is minimum
static int solve(int []array, int n, int K)
{
int start = 1;
for (int i = 0; i < n; ++i) {
if (array[i] > start)
start = array[i]; //Max subarray sum, considering subarray of length 1
}
int end = 0;
for (int i = 0; i < n; i++)
{
end += array[i]; //Max subarray sum, considering subarray of length n
}
// Answer stores possible
// maximum sub array sum
int answer = 0;
while (start <= end)
{
int mid = (start + end) / 2;
// If mid is possible solution
// Put answer = mid;
if (check(mid, array, n, K))
{
answer = mid;
end = mid - 1;
}
else
{
start = mid + 1;
}
}
return answer;
}
// Driver Code
public static void Main (String[] args)
{
int []array = { 1, 2, 3, 4 };
int n = array.Length ;
int K = 3;
Console.WriteLine(solve(array, n, K));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation of the above approach
// Function to check if mid can
// be maximum sub - arrays sum
function check(mid, array, n, K)
{
var count = 0;
var sum = 0;
for (var i = 0; i < n; i++) {
// If individual element is greater
// maximum possible sum
if (array[i] > mid)
return false;
// Increase sum of current sub - array
sum += array[i];
// If the sum is greater than
// mid increase count
if (sum > mid) {
count++;
sum = array[i];
}
}
count++;
// Check condition
if (count <= K)
return true;
return false;
}
// Function to find maximum subarray sum
// which is minimum
function solve(array, n, K)
{
var max = array.reduce((a,b)=>Math.max(a,b));
var start = max; //Max subarray sum, considering subarray of length 1
var end = 0;
for (var i = 0; i < n; i++) {
end += array[i]; //Max subarray sum, considering subarray of length n
}
// Answer stores possible
// maximum sub array sum
var answer = 0;
while (start <= end) {
var mid = parseInt((start + end) / 2);
// If mid is possible solution
// Put answer = mid;
if (check(mid, array, n, K)) {
answer = mid;
end = mid - 1;
}
else {
start = mid + 1;
}
}
return answer;
}
// Driver Code
var array = [1, 2, 3, 4];
var n = array.length;
var K = 3;
document.write( solve(array, n, K));
</script>
Producción
4
Complejidad de tiempo: O(N*log(Sum))
Donde N es el número de elementos de la array y Sum es la suma de todos los elementos de la array.