EN BÜYÜK TOPLAM BITIŞIK ARTAN ALT DIZI

GfG Practice'de deneyin ' title=

#practiceLinkDiv { görüntü: yok !önemli; }

N pozitif farklı tam sayılardan oluşan bir dizi verildiğinde. Sorun, O(n) zaman karmaşıklığında bitişik artan alt dizilerin en büyük toplamını bulmaktır.

Örnekler:

    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 Açgözlü Tilki Deneyin!

A basit çözüm öyle tüm alt dizileri oluştur ve toplamlarını hesaplayın. Son olarak alt diziyi maksimum toplamla döndürün. Bu çözümün zaman karmaşıklığı O(n)²).

Bir verimli çözüm tüm unsurların olumlu olduğu gerçeğine dayanmaktadır. Bu yüzden en uzun artan alt dizileri dikkate alıyoruz ve toplamlarını karşılaştırıyoruz. Artan alt diziler üst üste gelemediği için zaman karmaşıklığımız O(n) olur.

Algoritma:

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

Yukarıdaki algoritmanın uygulaması aşağıdadır.

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

Çıkış

Largest sum = 12

Zaman Karmaşıklığı : O(n)