Suma més gran contigua subbarray creixent
Prova-ho a GfG Practice 
#practiceLinkDiv { mostrar: cap !important; }
#practiceLinkDiv { mostrar: cap !important; } Donada una matriu de n nombres enters diferents positius. El problema és trobar la suma més gran de subarrays creixents contigües en complexitat temporal O(n).
Exemples:
Input : arr[] = {2 1 4 7 3 6}
Output : 12
Contiguous Increasing subarray {1 4 7} = 12
Input : arr[] = {38 7 8 10 12}
Output : 38
Recommended Practice Guineu cobdiciosa Prova-ho!A solució senzilla és a genera tots els subbarrays i calculen les seves sumes. Finalment retorna el subarray amb la suma màxima. La complexitat temporal d'aquesta solució és O(n 2 ).
An solució eficient es basa en el fet que tots els elements són positius. Per tant, considerem els subbarrays més llargs i comparem les seves sumes. L'augment de subbarrays no es pot solapar, de manera que la nostra complexitat temporal es converteix en O(n).
Algorisme:
Let arr be the array of size n
Let result be the required sum
int largestSum(arr n)
result = INT_MIN // Initialize result
i = 0
while i < n
// Find sum of longest increasing subarray
// starting with i
curr_sum = arr[i];
while i+1 < n && arr[i] < arr[i+1]
curr_sum += arr[i+1];
i++;
// If current sum is greater than current
// result.
if result < curr_sum
result = curr_sum;
i++;
return result
A continuació es mostra la implementació de l'algorisme anterior.
C++Java// C++ implementation of largest sum // contiguous increasing subarray #includeusing namespace std ; // Returns sum of longest // increasing subarray. int largestSum ( int arr [] int n ) { // Initialize result int result = INT_MIN ; // Note that i is incremented // by inner loop also so overall // time complexity is O(n) for ( int i = 0 ; i < n ; i ++ ) { // Find sum of longest // increasing subarray // starting from arr[i] int curr_sum = arr [ i ]; while ( i + 1 < n && arr [ i + 1 ] > arr [ i ]) { curr_sum += arr [ i + 1 ]; i ++ ; } // Update result if required if ( curr_sum > result ) result = curr_sum ; } // required largest sum return result ; } // Driver Code int main () { int arr [] = { 1 1 4 7 3 6 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < 'Largest sum = ' < < largestSum ( arr n ); return 0 ; } Python3// Java implementation of largest sum // contiguous increasing subarray class GFG { // Returns sum of longest // increasing subarray. static int largestSum ( int arr [] int n ) { // Initialize result int result = - 9999999 ; // Note that i is incremented // by inner loop also so overall // time complexity is O(n) for ( int i = 0 ; i < n ; i ++ ) { // Find sum of longest // increasing subarray // starting from arr[i] int curr_sum = arr [ i ] ; while ( i + 1 < n && arr [ i + 1 ] > arr [ i ] ) { curr_sum += arr [ i + 1 ] ; i ++ ; } // Update result if required if ( curr_sum > result ) result = curr_sum ; } // required largest sum return result ; } // Driver Code public static void main ( String [] args ) { int arr [] = { 1 1 4 7 3 6 }; int n = arr . length ; System . out . println ( 'Largest sum = ' + largestSum ( arr n )); } }C## Python3 implementation of largest # sum contiguous increasing subarray # Returns sum of longest # increasing subarray. def largestSum ( arr n ): # Initialize result result = - 2147483648 # Note that i is incremented # by inner loop also so overall # time complexity is O(n) for i in range ( n ): # Find sum of longest increasing # subarray starting from arr[i] curr_sum = arr [ i ] while ( i + 1 < n and arr [ i + 1 ] > arr [ i ]): curr_sum += arr [ i + 1 ] i += 1 # Update result if required if ( curr_sum > result ): result = curr_sum # required largest sum return result # Driver Code arr = [ 1 1 4 7 3 6 ] n = len ( arr ) print ( 'Largest sum = ' largestSum ( arr n )) # This code is contributed by Anant Agarwal.JavaScript// C# implementation of largest sum // contiguous increasing subarray using System ; class GFG { // Returns sum of longest // increasing subarray. static int largestSum ( int [] arr int n ) { // Initialize result int result = - 9999999 ; // Note that i is incremented by // inner loop also so overall // time complexity is O(n) for ( int i = 0 ; i < n ; i ++ ) { // Find sum of longest increasing // subarray starting from arr[i] int curr_sum = arr [ i ]; while ( i + 1 < n && arr [ i + 1 ] > arr [ i ]) { curr_sum += arr [ i + 1 ]; i ++ ; } // Update result if required if ( curr_sum > result ) result = curr_sum ; } // required largest sum return result ; } // Driver code public static void Main () { int [] arr = { 1 1 4 7 3 6 }; int n = arr . Length ; Console . Write ( 'Largest sum = ' + largestSum ( arr n )); } } // This code is contributed // by Nitin Mittal.PHP< script > // Javascript implementation of largest sum // contiguous increasing subarray // Returns sum of longest // increasing subarray. function largestSum ( arr n ) { // Initialize result var result = - 1000000000 ; // Note that i is incremented // by inner loop also so overall // time complexity is O(n) for ( var i = 0 ; i < n ; i ++ ) { // Find sum of longest // increasing subarray // starting from arr[i] var curr_sum = arr [ i ]; while ( i + 1 < n && arr [ i + 1 ] > arr [ i ]) { curr_sum += arr [ i + 1 ]; i ++ ; } // Update result if required if ( curr_sum > result ) result = curr_sum ; } // required largest sum return result ; } // Driver Code var arr = [ 1 1 4 7 3 6 ]; var n = arr . length ; document . write ( 'Largest sum = ' + largestSum ( arr n )); // This code is contributed by itsok. < /script>
SortidaLargest sum = 12Complexitat temporal: O(n)
Suma més gran contigua subbarray creixent Usant Recursió :
Algorisme recursiu per resoldre aquest problema:
Aquí teniu l'algoritme pas a pas del problema:
- La funció 'suma més gran' pren matriu 'arr' i la seva mida és 'n'.
- Si 'n==1' després torna arr[0]è element.
- Si 'n != 1' després una recursiu crida a la funció 'suma més gran' per trobar la suma més gran del subarray 'arr[0...n-1]' excloent l'últim element 'arr[n-1]' .
- Iterant sobre la matriu en ordre invers començant amb l'últim element, calculeu la suma de la subarray creixent que acaba a 'arr[n-1]' . Si un element és més petit que el següent, s'ha d'afegir a la suma actual. En cas contrari, el bucle s'hauria de trencar.
- A continuació, retorneu el màxim de la suma més gran, és a dir. 'retorna màx.(sum_max_sum curr_sum);' .
Aquí teniu la implementació de l'algorisme anterior:
C++C#includeusing namespace std ; // Recursive function to find the largest sum // of contiguous increasing subarray int largestSum ( int arr [] int n ) { // Base case if ( n == 1 ) return arr [ 0 ]; // Recursive call to find the largest sum int max_sum = max ( largestSum ( arr n - 1 ) arr [ n - 1 ]); // Compute the sum of the increasing subarray int curr_sum = arr [ n - 1 ]; for ( int i = n - 2 ; i >= 0 ; i -- ) { if ( arr [ i ] < arr [ i + 1 ]) curr_sum += arr [ i ]; else break ; } // Return the maximum of the largest sum so far // and the sum of the current increasing subarray return max ( max_sum curr_sum ); } // Driver Code int main () { int arr [] = { 1 1 4 7 3 6 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < 'Largest sum = ' < < largestSum ( arr n ); return 0 ; } // This code is contributed by Vaibhav Saroj. Java#include#include // Returns sum of longest increasing subarray int largestSum ( int arr [] int n ) { // Initialize result int result = INT_MIN ; // Note that i is incremented // by inner loop also so overall // time complexity is O(n) for ( int i = 0 ; i < n ; i ++ ) { // Find sum of longest // increasing subarray // starting from arr[i] int curr_sum = arr [ i ]; while ( i + 1 < n && arr [ i + 1 ] > arr [ i ]) { curr_sum += arr [ i + 1 ]; i ++ ; } // Update result if required if ( curr_sum > result ) result = curr_sum ; } // required largest sum return result ; } // Driver code int main () { int arr [] = { 1 1 4 7 3 6 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); printf ( 'Largest sum = %d n ' largestSum ( arr n )); return 0 ; } // This code is contributed by Vaibhav Saroj. Python/*package whatever //do not write package name here */ import java.util.* ; public class Main { // Recursive function to find the largest sum // of contiguous increasing subarray public static int largestSum ( int arr [] int n ) { // Base case if ( n == 1 ) return arr [ 0 ] ; // Recursive call to find the largest sum int max_sum = Math . max ( largestSum ( arr n - 1 ) arr [ n - 1 ] ); // Compute the sum of the increasing subarray int curr_sum = arr [ n - 1 ] ; for ( int i = n - 2 ; i >= 0 ; i -- ) { if ( arr [ i ] < arr [ i + 1 ] ) curr_sum += arr [ i ] ; else break ; } // Return the maximum of the largest sum so far // and the sum of the current increasing subarray return Math . max ( max_sum curr_sum ); } // Driver code public static void main ( String [] args ) { int arr [] = { 1 1 4 7 3 6 }; int n = arr . length ; System . out . println ( 'Largest sum = ' + largestSum ( arr n )); } } // This code is contributed by Vaibhav Saroj.C#def largestSum ( arr n ): # Base case if n == 1 : return arr [ 0 ] # Recursive call to find the largest sum max_sum = max ( largestSum ( arr n - 1 ) arr [ n - 1 ]) # Compute the sum of the increasing subarray curr_sum = arr [ n - 1 ] for i in range ( n - 2 - 1 - 1 ): if arr [ i ] < arr [ i + 1 ]: curr_sum += arr [ i ] else : break # Return the maximum of the largest sum so far # and the sum of the current increasing subarray return max ( max_sum curr_sum ) # Driver code arr = [ 1 1 4 7 3 6 ] n = len ( arr ) print ( 'Largest sum =' largestSum ( arr n )) # This code is contributed by Vaibhav Saroj.JavaScript// C# program for above approach using System ; public static class GFG { // Recursive function to find the largest sum // of contiguous increasing subarray public static int largestSum ( int [] arr int n ) { // Base case if ( n == 1 ) return arr [ 0 ]; // Recursive call to find the largest sum int max_sum = Math . Max ( largestSum ( arr n - 1 ) arr [ n - 1 ]); // Compute the sum of the increasing subarray int curr_sum = arr [ n - 1 ]; for ( int i = n - 2 ; i >= 0 ; i -- ) { if ( arr [ i ] < arr [ i + 1 ]) curr_sum += arr [ i ]; else break ; } // Return the maximum of the largest sum so far // and the sum of the current increasing subarray return Math . Max ( max_sum curr_sum ); } // Driver code public static void Main () { int [] arr = { 1 1 4 7 3 6 }; int n = arr . Length ; Console . WriteLine ( 'Largest sum = ' + largestSum ( arr n )); } } // This code is contributed by Utkarsh KumarPHPfunction largestSum ( arr n ) { // Base case if ( n == 1 ) return arr [ 0 ]; // Recursive call to find the largest sum let max_sum = Math . max ( largestSum ( arr n - 1 ) arr [ n - 1 ]); // Compute the sum of the increasing subarray let curr_sum = arr [ n - 1 ]; for ( let i = n - 2 ; i >= 0 ; i -- ) { if ( arr [ i ] < arr [ i + 1 ]) curr_sum += arr [ i ]; else break ; } // Return the maximum of the largest sum so far // and the sum of the current increasing subarray return Math . max ( max_sum curr_sum ); } // Driver Code let arr = [ 1 1 4 7 3 6 ]; let n = arr . length ; console . log ( 'Largest sum = ' + largestSum ( arr n ));
SortidaLargest sum = 12Complexitat temporal: O(n^2).
Complexitat espacial: O(n).Suma més gran subbarray creixent contigua Utilitzant l'algoritme de Kadane:-
Per obtenir la suma més gran s'utilitza l'enfocament de Kadane, però pressuposa que la matriu conté valors tant positius com negatius. En aquest cas hem de canviar l'algorisme perquè només funcioni en subbarrays ascendents contigus.
A continuació s'explica com podem modificar l'algoritme de Kadane per trobar la suma més gran contigua de subarray creixent:
C++
- Inicialitzeu dues variables: max_sum i curr_sum al primer element de la matriu.
- Recorre la matriu començant pel segon element.
- si l'element actual és més gran que l'element anterior, afegiu-lo a curr_sum. En cas contrari, restabliu curr_sum a l'element actual.
- Si curr_sum és més gran que max_sum actualitzeu max_sum.
- Després del bucle, max_sum contindrà la suma més gran contigua subbarray creixent.
Java#includeusing namespace std ; int largest_sum_contiguous_increasing_subarray ( int arr [] int n ) { int max_sum = arr [ 0 ]; int curr_sum = arr [ 0 ]; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] > arr [ i -1 ]) { curr_sum += arr [ i ]; } else { curr_sum = arr [ i ]; } if ( curr_sum > max_sum ) { max_sum = curr_sum ; } } return max_sum ; } int main () { int arr [] = { 1 1 4 7 3 6 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < largest_sum_contiguous_increasing_subarray ( arr n ) < < endl ; // Output: 44 (1+2+3+5+7+8+9+10) return 0 ; } Python3public class Main { public static int largestSumContiguousIncreasingSubarray ( int [] arr int n ) { int maxSum = arr [ 0 ] ; int currSum = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] > arr [ i - 1 ] ) { currSum += arr [ i ] ; } else { currSum = arr [ i ] ; } if ( currSum > maxSum ) { maxSum = currSum ; } } return maxSum ; } public static void main ( String [] args ) { int [] arr = { 1 1 4 7 3 6 }; int n = arr . length ; System . out . println ( largestSumContiguousIncreasingSubarray ( arr n )); // Output: 44 (1+2+3+5+7+8+9+10) } }C#def largest_sum_contiguous_increasing_subarray ( arr n ): max_sum = arr [ 0 ] curr_sum = arr [ 0 ] for i in range ( 1 n ): if arr [ i ] > arr [ i - 1 ]: curr_sum += arr [ i ] else : curr_sum = arr [ i ] if curr_sum > max_sum : max_sum = curr_sum return max_sum arr = [ 1 1 4 7 3 6 ] n = len ( arr ) print ( largest_sum_contiguous_increasing_subarray ( arr n )) #output 12 (1+4+7)JavaScriptusing System ; class GFG { // Function to find the largest sum of a contiguous // increasing subarray static int LargestSumContiguousIncreasingSubarray ( int [] arr int n ) { int maxSum = arr [ 0 ]; // Initialize the maximum sum // and current sum int currSum = arr [ 0 ]; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] > arr [ i - 1 ]) // Check if the current // element is greater than the // previous element { currSum += arr [ i ]; // If increasing add the // element to the current sum } else { currSum = arr [ i ]; // If not increasing start a // new increasing subarray // from the current element } if ( currSum > maxSum ) // Update the maximum sum if the // current sum is greater { maxSum = currSum ; } } return maxSum ; } static void Main () { int [] arr = { 1 1 4 7 3 6 }; int n = arr . Length ; Console . WriteLine ( LargestSumContiguousIncreasingSubarray ( arr n )); } } // This code is contributed by akshitaguprzj3
Sortida12Complexitat temporal: O(n).
Crea un qüestionari
Complexitat espacial: O(1).
