Se le da una array unidimensional que puede contener enteros positivos y negativos, encuentre la suma de subarreglo contiguo de números que tiene la suma más grande.
Por ejemplo, si el arreglo dado es {-2, -5, 6, -2, -3, 1, 5 , -6}, entonces la suma máxima del subarreglo es 7 (ver elementos resaltados).
C++
// A Divide and Conquer based program for maximum subarray // sum problem #include <limits.h> #include <stdio.h> // A utility function to find maximum of two integers int max(int a, int b) { return (a > b) ? a : b; } // A utility function to find maximum of three integers int max(int a, int b, int c) { return max(max(a, b), c); } // Find the maximum possible sum in arr[] such that arr[m] // is part of it int maxCrossingSum(int arr[], int l, int m, int h) { // Include elements on left of mid. int sum = 0; int left_sum = INT_MIN; for (int i = m; i >= l; i--) { sum = sum + arr[i]; if (sum > left_sum) left_sum = sum; } // Include elements on right of mid sum = 0; int right_sum = INT_MIN; for (int i = m + 1; i <= h; i++) { sum = sum + arr[i]; if (sum > right_sum) right_sum = sum; } // Return sum of elements on left and right of mid // returning only left_sum + right_sum will fail for // [-2, 1] return max(left_sum + right_sum, left_sum, right_sum); } // Returns sum of maximum sum subarray in aa[l..h] int maxSubArraySum(int arr[], int l, int h) { // Base Case: Only one element if (l == h) return arr[l]; // Find middle point int m = (l + h) / 2; /* Return maximum of following three possible cases a) Maximum subarray sum in left half b) Maximum subarray sum in right half c) Maximum subarray sum such that the subarray crosses the midpoint */ return max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m + 1, h), maxCrossingSum(arr, l, m, h)); } /*Driver program to test maxSubArraySum*/ int main() { int arr[] = { 2, 3, 4, 5, 7 }; int n = sizeof(arr) / sizeof(arr[0]); int max_sum = maxSubArraySum(arr, 0, n - 1); printf("Maximum contiguous sum is %d\n", max_sum); getchar(); return 0; }
Java
// A Divide and Conquer based Java // program for maximum subarray sum // problem import java.util.*; class GFG { // Find the maximum possible sum in arr[] // such that arr[m] is part of it static int maxCrossingSum(int arr[], int l, int m, int h) { // Include elements on left of mid. int sum = 0; int left_sum = Integer.MIN_VALUE; for (int i = m; i >= l; i--) { sum = sum + arr[i]; if (sum > left_sum) left_sum = sum; } // Include elements on right of mid sum = 0; int right_sum = Integer.MIN_VALUE; for (int i = m + 1; i <= h; i++) { sum = sum + arr[i]; if (sum > right_sum) right_sum = sum; } // Return sum of elements on left // and right of mid // returning only left_sum + right_sum will fail for // [-2, 1] return Math.max(left_sum + right_sum, Math.max(left_sum, right_sum)); } // Returns sum of maximum sum subarray // in aa[l..h] static int maxSubArraySum(int arr[], int l, int h) { // Base Case: Only one element if (l == h) return arr[l]; // Find middle point int m = (l + h) / 2; /* Return maximum of following three possible cases: a) Maximum subarray sum in left half b) Maximum subarray sum in right half c) Maximum subarray sum such that the subarray crosses the midpoint */ return Math.max( Math.max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m + 1, h)), maxCrossingSum(arr, l, m, h)); } /* Driver program to test maxSubArraySum */ public static void main(String[] args) { int arr[] = { 2, 3, 4, 5, 7 }; int n = arr.length; int max_sum = maxSubArraySum(arr, 0, n - 1); System.out.println("Maximum contiguous sum is " + max_sum); } } // This code is contributed by Prerna Saini
Python
# A Divide and Conquer based program # for maximum subarray sum problem # Find the maximum possible sum in # arr[] auch that arr[m] is part of it def maxCrossingSum(arr, l, m, h): # Include elements on left of mid. sm = 0 left_sum = -10000 for i in range(m, l-1, -1): sm = sm + arr[i] if (sm > left_sum): left_sum = sm # Include elements on right of mid sm = 0 right_sum = -1000 for i in range(m + 1, h + 1): sm = sm + arr[i] if (sm > right_sum): right_sum = sm # Return sum of elements on left and right of mid # returning only left_sum + right_sum will fail for [-2, 1] return max(left_sum + right_sum, left_sum, right_sum) # Returns sum of maximum sum subarray in aa[l..h] def maxSubArraySum(arr, l, h): # Base Case: Only one element if (l == h): return arr[l] # Find middle point m = (l + h) // 2 # Return maximum of following three possible cases # a) Maximum subarray sum in left half # b) Maximum subarray sum in right half # c) Maximum subarray sum such that the # subarray crosses the midpoint return max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m+1, h), maxCrossingSum(arr, l, m, h)) # Driver Code arr = [2, 3, 4, 5, 7] n = len(arr) max_sum = maxSubArraySum(arr, 0, n-1) print("Maximum contiguous sum is ", max_sum) # This code is contributed by Nikita Tiwari.
C#
// A Divide and Conquer based C# // program for maximum subarray sum // problem using System; class GFG { // Find the maximum possible sum in arr[] // such that arr[m] is part of it static int maxCrossingSum(int[] arr, int l, int m, int h) { // Include elements on left of mid. int sum = 0; int left_sum = int.MinValue; for (int i = m; i >= l; i--) { sum = sum + arr[i]; if (sum > left_sum) left_sum = sum; } // Include elements on right of mid sum = 0; int right_sum = int.MinValue; ; for (int i = m + 1; i <= h; i++) { sum = sum + arr[i]; if (sum > right_sum) right_sum = sum; } // Return sum of elements on left // and right of mid // returning only left_sum + right_sum will fail for // [-2, 1] return Math.Max(left_sum + right_sum, Math.Max(left_sum, right_sum)); } // Returns sum of maximum sum subarray // in aa[l..h] static int maxSubArraySum(int[] arr, int l, int h) { // Base Case: Only one element if (l == h) return arr[l]; // Find middle point int m = (l + h) / 2; /* Return maximum of following three possible cases: a) Maximum subarray sum in left half b) Maximum subarray sum in right half c) Maximum subarray sum such that the subarray crosses the midpoint */ return Math.Max( Math.Max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m + 1, h)), maxCrossingSum(arr, l, m, h)); } /* Driver program to test maxSubArraySum */ public static void Main() { int[] arr = { 2, 3, 4, 5, 7 }; int n = arr.Length; int max_sum = maxSubArraySum(arr, 0, n - 1); Console.Write("Maximum contiguous sum is " + max_sum); } } // This code is contributed by vt_m.
PHP
<?php // A Divide and Conquer based program // for maximum subarray sum problem // Find the maximum possible sum in arr[] // such that arr[m] is part of it function maxCrossingSum(&$arr, $l, $m, $h) { // Include elements on left of mid. $sum = 0; $left_sum = PHP_INT_MIN; for ($i = $m; $i >= $l; $i--) { $sum = $sum + $arr[$i]; if ($sum > $left_sum) $left_sum = $sum; } // Include elements on right of mid $sum = 0; $right_sum = PHP_INT_MIN; for ($i = $m + 1; $i <= $h; $i++) { $sum = $sum + $arr[$i]; if ($sum > $right_sum) $right_sum = $sum; } // Return sum of elements on left // and right of mid // returning only left_sum + right_sum will fail for [-2, 1] return max($left_sum + $right_sum, $left_sum, $right_sum); } // Returns sum of maximum sum // subarray in aa[l..h] function maxSubArraySum(&$arr, $l, $h) { // Base Case: Only one element if ($l == $h) return $arr[$l]; // Find middle point $m = intval(($l + $h) / 2); /* Return maximum of following three possible cases a) Maximum subarray sum in left half b) Maximum subarray sum in right half c) Maximum subarray sum such that the subarray crosses the midpoint */ return max(maxSubArraySum($arr, $l, $m), maxSubArraySum($arr, $m + 1, $h), maxCrossingSum($arr, $l, $m, $h)); } // Driver Code $arr = array(2, 3, 4, 5, 7); $n = count($arr); $max_sum = maxSubArraySum($arr, 0, $n - 1); echo "Maximum contiguous sum is " . $max_sum; // This code is contributed by rathbhupendra, Aadil ?>
Javascript
<script> // A Divide and Conquer based program for maximum subarray // sum problem // A utility function to find maximum of two integers function max(a,b) { return (a > b) ? a : b; } // A utility function to find maximum of three integers function max(a,b,c) { return Math.max(Math.max(a, b), c); } // Find the maximum possible sum in arr[] auch that arr[m] // is part of it function maxCrossingSum(arr, l, m,h) { // Include elements on left of mid. let sum = 0; let left_sum = Number.MIN_VALUE; for (let i = m; i >= l; i--) { sum = sum + arr[i]; if (sum > left_sum) left_sum = sum; } // Include elements on right of mid sum = 0; let right_sum = Number.MIN_VALUE; for (let i = m + 1; i <= h; i++) { sum = sum + arr[i]; if (sum > right_sum) right_sum = sum; } // Return sum of elements on left and right of mid // returning only left_sum + right_sum will fail for // [-2, 1] return max(left_sum + right_sum, left_sum, right_sum); } // Returns sum of maximum sum subarray in aa[l..h] function maxSubArraySum(arr, l,h) { // Base Case: Only one element if (l == h) return arr[l]; // Find middle point let m = parseInt((l + h) / 2, 10); /* Return maximum of following three possible cases a) Maximum subarray sum in left half b) Maximum subarray sum in right half c) Maximum subarray sum such that the subarray crosses the midpoint */ return max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m + 1, h), maxCrossingSum(arr, l, m, h)); } let arr = [ 2, 3, 4, 5, 7 ]; let n = arr.length; let max_sum = maxSubArraySum(arr, 0, n - 1); document.write("Maximum contiguous sum is " + max_sum); // This code is contributed by vaibhavrabadiya117. </script>
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