Dada una array de enteros no negativos y una suma. Tenemos que encontrar la suma del subarreglo que tiene una suma máxima menor o igual que la suma dada en el arreglo.
( Nota: la array dada contiene solo números enteros no negativos).
Ejemplos:
Input : arr[] = { 1, 2, 3, 4, 5 } sum = 11 Output : 10 Subarray having maximum sum is { 1, 2, 3, 4 } Input : arr[] = { 2, 4, 6, 8, 10 } sum = 7 Output : 6 Subarray having maximum sum is { 2, 4 } or { 6 }
Enfoque ingenuo: podemos encontrar la suma máxima del subarreglo ejecutando dos bucles. Pero la complejidad del tiempo será O(N*N).
Enfoque eficiente: el subarreglo que tiene la suma máxima se puede encontrar usando una ventana deslizante . Si curr_sum es menor que sum, incluya elementos de array. Si se vuelve mayor que la suma, elimina los elementos desde el inicio en curr_sum. (Esto funcionará solo en el caso de elementos no negativos).
Implementación:
C++
// C++ program to find subarray having // maximum sum less than or equal to sum #include <bits/stdc++.h> using namespace std; // To find subarray with maximum sum // less than or equal to sum int findMaxSubarraySum(int arr[], int n, int sum) { // To store current sum and // max sum of subarrays int curr_sum = arr[0], max_sum = 0, start = 0; // To find max_sum less than sum for (int i = 1; i < n; i++) { // Update max_sum if it becomes // greater than curr_sum if (curr_sum <= sum) max_sum = max(max_sum, curr_sum); // If curr_sum becomes greater than // sum subtract starting elements of array while (start < i && curr_sum + arr[i] > sum) { curr_sum -= arr[start]; start++; } // If cur_sum becomes negative then start new subarray if (curr_sum < 0) { curr_sum = 0; } // Add elements to curr_sum curr_sum += arr[i]; } // Adding an extra check for last subarray if (curr_sum <= sum) max_sum = max(max_sum, curr_sum); return max_sum; } // Driver program to test above function int main() { int arr[] = {6, 8, 9}; int n = sizeof(arr) / sizeof(arr[0]); int sum = 20; cout << findMaxSubarraySum(arr, n, sum); return 0; }
Java
// Java program to find subarray having // maximum sum less than or equal to sum public class Main { // To find subarray with maximum sum // less than or equal to sum static int findMaxSubarraySum(int arr[], int n, int sum) { // To store current sum and // max sum of subarrays int curr_sum = arr[0], max_sum = 0, start = 0; // To find max_sum less than sum for (int i = 1; i < n; i++) { // Update max_sum if it becomes // greater than curr_sum if (curr_sum <= sum) max_sum = Math.max(max_sum, curr_sum); // If curr_sum becomes greater than // sum subtract starting elements of array while (curr_sum + arr[i] > sum && start < i) { curr_sum -= arr[start]; start++; } // Add elements to curr_sum curr_sum += arr[i]; } // Adding an extra check for last subarray if (curr_sum <= sum) max_sum = Math.max(max_sum, curr_sum); return max_sum; } // Driver program to test above function public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5 }; int n = arr.length; int sum = 11; System.out.println(findMaxSubarraySum(arr, n, sum)); } }
Python3
# Python3 program to find subarray having # maximum sum less than or equal to sum # To find subarray with maximum sum # less than or equal to sum def findMaxSubarraySum(arr, n, sum): # To store current sum and # max sum of subarrays curr_sum = arr[0] max_sum = 0 start = 0; # To find max_sum less than sum for i in range(1, n): # Update max_sum if it becomes # greater than curr_sum if (curr_sum <= sum): max_sum = max(max_sum, curr_sum) # If curr_sum becomes greater than sum # subtract starting elements of array while (curr_sum + arr[i] > sum and start < i): curr_sum -= arr[start] start += 1 # Add elements to curr_sum curr_sum += arr[i] # Adding an extra check for last subarray if (curr_sum <= sum): max_sum = max(max_sum, curr_sum) return max_sum # Driver Code if __name__ == '__main__': arr = [6, 8, 9] n = len(arr) sum = 20 print(findMaxSubarraySum(arr, n, sum)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find subarray // having maximum sum less //than or equal to sum using System; public class GFG { // To find subarray with maximum // sum less than or equal // to sum static int findMaxSubarraySum(int []arr, int n, int sum) { // To store current sum and // max sum of subarrays int curr_sum = arr[0], max_sum = 0, start = 0; // To find max_sum less than sum for (int i = 1; i < n; i++) { // Update max_sum if it becomes // greater than curr_sum if (curr_sum <= sum) max_sum = Math.Max(max_sum, curr_sum); // If curr_sum becomes greater than // sum subtract starting elements of array while (curr_sum + arr[i] > sum && start < i) { curr_sum -= arr[start]; start++; } // Add elements to curr_sum curr_sum += arr[i]; } // Adding an extra check for last subarray if (curr_sum <= sum) max_sum = Math.Max(max_sum, curr_sum); return max_sum; } // Driver Code public static void Main() { int []arr = {1, 2, 3, 4, 5}; int n = arr.Length; int sum = 11; Console.Write(findMaxSubarraySum(arr, n, sum)); } } // This code is contributed by Nitin Mittal.
PHP
<?php // PHP program to find subarray having // maximum sum less than or equal to sum // To find subarray with maximum sum // less than or equal to sum function findMaxSubarraySum(&$arr, $n, $sum) { // To store current sum and // max sum of subarrays $curr_sum = $arr[0]; $max_sum = 0; $start = 0; // To find max_sum less than sum for ($i = 1; $i < $n; $i++) { // Update max_sum if it becomes // greater than curr_sum if ($curr_sum <= $sum) $max_sum = max($max_sum, $curr_sum); // If curr_sum becomes greater than // sum subtract starting elements of array while ($curr_sum + $arr[$i] > $sum && $start < $i) { $curr_sum -= $arr[$start]; $start++; } // Add elements to curr_sum $curr_sum += $arr[$i]; } // Adding an extra check for last subarray if ($curr_sum <= $sum) $max_sum = max($max_sum, $curr_sum); return $max_sum; } // Driver Code $arr = array(6, 8, 9); $n = sizeof($arr); $sum = 20; echo findMaxSubarraySum($arr, $n, $sum); // This code is contributed by ita_c ?>
Javascript
<script> // Javascript program to find subarray having // maximum sum less than or equal to sum // To find subarray with maximum sum // less than or equal to sum function findMaxSubarraySum(arr, n, sum) { // To store current sum and // max sum of subarrays let curr_sum = arr[0], max_sum = 0, start = 0; // To find max_sum less than sum for(let i = 1; i < n; i++) { // Update max_sum if it becomes // greater than curr_sum if (curr_sum <= sum) max_sum = Math.max(max_sum, curr_sum); // If curr_sum becomes greater than // sum subtract starting elements of array while (curr_sum + arr[i] > sum && start < i) { curr_sum -= arr[start]; start++; } // Add elements to curr_sum curr_sum += arr[i]; } // Adding an extra check for last subarray if (curr_sum <= sum) max_sum = Math.max(max_sum, curr_sum); return max_sum; } // Driver code let arr = [ 6, 8, 9 ]; let n = arr.length; let sum = 20; document.write(findMaxSubarraySum(arr, n, sum)); // This code is contributed by Mayank Tyagi </script>
17
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Si se proporciona una array con todos los tipos (positivo, negativo o cero) de elementos, podemos usar la suma y los conjuntos de prefijos y la complejidad de tiempo en el peor de los casos será O (n.log (n)). Puede hacer referencia a la suma máxima de subarreglo menor o igual a k usando el artículo establecido para una mayor claridad de este método.
Este artículo es una contribución de nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA