logo

TechCodeview

Grootste som aaneengesloten toenemende subarray

Probeer het eens op GfG Practice ' title= #practiceLinkDiv {weergave: geen! belangrijk; }

Gegeven een array van n positieve afzonderlijke gehele getallen. Het probleem is om de grootste som van aaneengesloten toenemende subarrays in O(n)-tijdcomplexiteit te vinden.

Voorbeelden:  

    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 Hebzuchtige Vos Probeer het!

A eenvoudige oplossing is om alle subarrays genereren en bereken hun sommen. Geef ten slotte de subarray met de maximale som terug. De tijdscomplexiteit van deze oplossing is O(n2).



bereid je voor op testmockito

Een efficiënte oplossing is gebaseerd op het feit dat alle elementen positief zijn. We beschouwen dus de langst toenemende subarrays en vergelijken hun sommen. Het vergroten van subarrays kan niet overlappen, dus onze tijdscomplexiteit wordt O(n).

Algoritme:  

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

Hieronder vindt u de implementatie van het bovenstaande algoritme.

cast string als int
C++ 
// C++ implementation of largest sum // contiguous increasing subarray #include    using 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; }
Java 
// 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));  } }
Python3 
# 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.
C# 
// 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.
JavaScript 
<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>
PHP 
 // PHP implementation of largest sum // contiguous increasing subarray // Returns sum of longest  // increasing subarray. function largestSum($arr $n) { $INT_MIN = 0; // Initialize result $result = $INT_MIN; // Note that i is incremented  // by inner loop also so overall // time complexity is O(n) for ($i = 0; $i < $n; $i++) { // Find sum of longest  // increasing subarray // starting from arr[i] $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 { $arr = array(1 1 4 7 3 6); $n = sizeof($arr) / sizeof($arr[0]); echo 'Largest sum = '  largestSum($arr $n); return 0; } // This code is contributed by nitin mittal. ?>

Uitvoer 
Largest sum = 12

Tijdcomplexiteit: O(n)

 

Grootste som aaneengesloten toenemende subarray Gebruikt Recursie : 

Recursief algoritme om dit probleem op te lossen:

Hier is het stapsgewijze algoritme van het probleem:

  1. De functie 'grootste som' neemt array 'arr' en de maat is 'N'.
  2. Als   'n==1' keer dan terug arr[0]de element.
  3. Als 'n != 1' dan roept een recursieve functie de functie aan 'grootste som'   om de grootste som van de subarray te vinden 'arr[0...n-1]' met uitzondering van het laatste element 'arr[n-1]' .
  4.  Door de array in omgekeerde volgorde te doorlopen, te beginnen met het voorlaatste element, bereken je de som van de toenemende subarray eindigend op 'arr[n-1]' . Als het ene element kleiner is dan het volgende, moet het bij de huidige som worden opgeteld. Anders moet de lus worden verbroken.
  5. Retourneer vervolgens het maximum van het grootste bedrag, d.w.z. ' return max(max_sum curr_sum);' .
     

Hier is de implementatie van het bovenstaande algoritme:

C++ 
#include    using 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.
C 
#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 = %dn' largestSum(arr n));  return 0; } // This code is contributed by Vaibhav Saroj.
Java 
/*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.
Python 
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.
C# 
// 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 Kumar
JavaScript 
function 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));
PHP 
 // Recursive function to find the largest sum // of contiguous increasing subarray function 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 = $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 $arr = array(1 1 4 7 3 6); $n = count($arr); echo 'Largest sum = ' . largestSum($arr $n); ?>

Uitvoer 
Largest sum = 12

Tijdcomplexiteit: O(n^2).
Ruimtecomplexiteit: Op).

Grootste som aaneengesloten toenemende subarray Met behulp van Kadane's algoritme: -

Om de subarray met de grootste som te krijgen, wordt de benadering van Kadane gebruikt, maar deze veronderstelt dat de array zowel positieve als negatieve waarden bevat. In dit geval moeten we het algoritme zo veranderen dat het alleen werkt op aaneengesloten stijgende subarrays.

Hieronder ziet u hoe we het algoritme van Kadane kunnen aanpassen om de grootste som aaneengesloten toenemende subarray te vinden:

  1. Initialiseer twee variabelen: max_sum en curr_sum naar het eerste element van de array.
  2. Loop door de array, beginnend bij het tweede element.
  3. als het huidige element groter is dan het vorige element, voeg het dan toe aan de curr_sum. Reset anders curr_sum naar het huidige element.
  4. Als curr_sum groter is dan max_sum, update max_sum.
  5. Na de lus zal max_sum de grootste som aaneengesloten toenemende subarray bevatten.
     
C++ 
#include    using 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; }
Java 
public 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)  } }
Python3 
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)
C# 
using 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
JavaScript 
 // Javascript code for above approach    // Function to find the largest sum of a contiguous  // increasing subarray  function LargestSumContiguousIncreasingSubarray(arr n)  {  let maxSum = arr[0]; // Initialize the maximum sum  // and current sum  let currSum = arr[0];    for (let 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;  }    let arr = [ 1 1 4 7 3 6 ];  let n = arr.length;  console.log(LargestSumContiguousIncreasingSubarray(arr n));      // This code is contributed by Pushpesh Raj

Uitvoer 
12

Tijdcomplexiteit: O(n).
Ruimtecomplexiteit: O(1).

wanneer werd de school uitgevonden?
Quiz maken