Sous-tableau croissant contigu à la plus grande somme
Essayez-le sur GfG Practice 
#practiceLinkDiv { display : aucun !important; }
#practiceLinkDiv { display : aucun !important; } Étant donné un tableau de n entiers distincts positifs. Le problème est de trouver la plus grande somme de sous-tableaux croissants contigus en complexité temporelle 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 Renard gourmand Essayez-le !UN solution simple est de générer tous les sous-tableaux et calculer leurs sommes. Enfin, renvoyez le sous-tableau avec la somme maximale. La complexité temporelle de cette solution est O(n 2 ).
Un solution efficace repose sur le fait que tous les éléments sont positifs. Nous considérons donc les sous-tableaux croissants les plus longs et comparons leurs sommes. Les sous-tableaux croissants ne peuvent pas se chevaucher, notre complexité temporelle devient donc O (n).
Algorithme:
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
Vous trouverez ci-dessous la mise en œuvre de l'algorithme ci-dessus.
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>
SortirLargest sum = 12Complexité temporelle : O(n)
Sous-tableau croissant contigu à la plus grande sommeUtilisation Récursivité :
Algorithme récursif pour résoudre ce problème :
Voici l'algorithme étape par étape du problème :
- La fonction 'la plus grande somme' prend un tableau 'arr' et sa taille est 'n'.
- Si 'n==1' puis reviens arr[0]ième élément.
- Si 'n != 1' puis un appel récursif à la fonction 'la plus grande somme' trouver la plus grande somme du sous-tableau 'arr[0...n-1]' à l'exclusion du dernier élément 'arr[n-1]' .
- En parcourant le tableau dans l'ordre inverse en commençant par l'avant-dernier élément, calculez la somme du sous-tableau croissant se terminant à 'arr[n-1]' . Si un élément est plus petit que le suivant, il doit être ajouté à la somme actuelle. Sinon, la boucle devrait être rompue.
- Renvoyez ensuite le maximum de la plus grande somme, c'est-à-dire 'retour max(max_sum curr_sum);' .
Voici l'implémentation de l'algorithme ci-dessus :
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 ));
SortirLargest sum = 12Complexité temporelle : O(n^2).
Complexité spatiale : Sur).Sous-tableau croissant contigu à la plus grande somme utilisant l'algorithme de Kadane : -
Pour obtenir le sous-tableau de somme le plus grand, l'approche de Kadane est utilisée, mais elle présuppose que le tableau contienne à la fois des valeurs positives et négatives. Dans ce cas, nous devons modifier l'algorithme pour qu'il ne fonctionne que sur des sous-réseaux ascendants contigus.
Voici comment nous pouvons modifier l'algorithme de Kadane pour trouver le sous-tableau croissant contigu à la plus grande somme :
C++
- Initialisez deux variables : max_sum et curr_sum au premier élément du tableau.
- Parcourez le tableau en commençant par le deuxième élément.
- si l'élément actuel est supérieur à l'élément précédent, ajoutez-le au curr_sum. Sinon, réinitialisez curr_sum à l'élément actuel.
- Si curr_sum est supérieur à max_sum, mettez à jour max_sum.
- Après la boucle, max_sum contiendra le sous-tableau croissant contigu à la plus grande somme.
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
Sortir12Complexité temporelle : O(n).
Créer un quiz
Complexité spatiale : O(1).
![Méthode Java main() – public static void main (String[] args)](https://techcodeview.com/img/java-basics/92/java-main-method-public-static-void-main.webp)
