STØRSTE SUM SAMMENHÆNGENDE STIGENDE SUBARRAY

Prøv det på GfG Practice ' title=

#practiceLinkDiv { display: ingen !important; }

Givet en matrix af n positive distinkte heltal. Problemet er at finde den største sum af sammenhængende stigende 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ådige ræv Prøv det!

EN enkel løsning er til generere alle underarrays og beregne deres beløb. Til sidst returnerer subarrayet med maksimal sum. Tidskompleksiteten af denne løsning er O(n²).

An effektiv løsning er baseret på, at alle elementer er positive. Så vi overvejer længst voksende subarrays og sammenligner deres summer. Til stigende subarrays kan ikke overlappe, så vores tidskompleksitet bliver 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 af ovenstående algoritme.

hashmap java

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

Produktion

Largest sum = 12

Tidskompleksitet: O(n)