STØRSTE SUM SAMMENHENGENDE ØKENDE UNDERGRUPPE

Prøv det på GfG Practice ' title=

#practiceLinkDiv { display: ingen !viktig; }

Gitt en matrise med n positive distinkte heltall. Problemet er å finne den største summen av sammenhengende økende subarray i O(n) tidskompleksitet.

Eksempler:

    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 Grådig rev Prøv det!

EN enkel løsning er å generere alle undermatriser og beregne summene deres. Returner til slutt subarrayen med maksimal sum. Tidskompleksiteten til denne løsningen er O(n²).

An effektiv løsning er basert på at alle elementer er positive. Så vi vurderer de lengst økende undergruppene og sammenligner summene deres. Til økende subarrays kan ikke overlappe, så vår tidskompleksitet blir 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

Nedenfor er implementeringen av algoritmen ovenfor.

forhåndsbestill traversering

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# 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. ?>

Produksjon

Largest sum = 12

Tidskompleksitet: O(n)