#practiceLinkDiv { display: none !important; }Dots n pozitīvu atšķirīgu veselu skaitļu masīvs. Problēma ir atrast lielāko blakusesošo pieaugošo apakšgrupu summu O(n) laika sarežģītībā.
Piemēri:
Input : arr[] = {2 1 4 7 3 6}Recommended Practice Mantkārīgā Lapsa Izmēģiniet to!
Output : 12
Contiguous Increasing subarray {1 4 7} = 12
Input : arr[] = {38 7 8 10 12}
Output : 38
A vienkāršs risinājums ir uz ģenerēt visus apakšblokus un aprēķināt to summas. Visbeidzot atgrieziet apakšgrupu ar maksimālo summu. Šī risinājuma laika sarežģītība ir O(n2).
An efektīvs risinājums ir balstīts uz faktu, ka visi elementi ir pozitīvi. Tāpēc mēs ņemam vērā visilgāk augošās apakšgrupas un salīdzinām to summas. Lai palielinātu apakšgrupas, tās nevar pārklāties, tāpēc mūsu laika sarežģītība kļūst par O (n).
Algoritms:
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
Zemāk ir aprakstīta iepriekš minētā algoritma ieviešana.
C++// C++ implementation of largest sum // contiguous increasing subarray #include
// 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 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.
<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 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. ?> Izvade
Largest sum = 12
Laika sarežģītība: O(n)
Lielākā summa blakus esošā pieaugošā apakšgrupa Izmantojot Rekursija :
Rekursīvais algoritms šīs problēmas risināšanai:
Šeit ir soli pa solim problēmas algoritms:
- Funkcija 'largestSum' aizņem masīvu 'arr' un tā izmērs ir 'n'.
- Ja 'n==1' tad atgriezies arr[0]th elements.
- Ja 'n != 1' tad rekursīvs funkcijas izsaukums 'largestSum' lai atrastu apakšgrupas lielāko summu "arr[0...n-1]" izņemot pēdējo elementu "arr[n-1]" .
- Atkārtojot masīvu apgrieztā secībā, sākot ar otro pēdējo elementu, aprēķiniet pieaugošā apakšmasīva summu, kas beidzas ar "arr[n-1]" . Ja viens elements ir mazāks par nākamo, tas jāpievieno pašreizējai summai. Pretējā gadījumā cilpa ir jāpārtrauc.
- Pēc tam atgriež lielākās summas maksimumu, t.i. ' return max(max_sum curr_sum);' .
Šeit ir aprakstīta iepriekš minētā algoritma ieviešana:
C++#include
#include
/*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.
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# 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
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));
// 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); ?> Izvade
Largest sum = 12
Laika sarežģītība: O(n^2).
Telpas sarežģītība: O(n).
Lielākā summa blakusesoša pieaugošā apakšgrupa Izmantojot Kadānas algoritmu:-
Lai iegūtu lielākās summas apakšmasu, tiek izmantota Kadane pieeja, tomēr tā paredz, ka masīvā ir gan pozitīvas, gan negatīvas vērtības. Šajā gadījumā mums ir jāmaina algoritms, lai tas darbotos tikai uz blakus esošajiem augošajiem apakšblokiem.
Tālāk ir norādīts, kā mēs varam modificēt Kadane algoritmu, lai atrastu lielāko blakusesošo pieaugošo apakšgrupu:
- Inicializējiet divus mainīgos: max_sum un curr_sum uz pirmo masīva elementu.
- Apmeklējiet masīvu, sākot no otrā elementa.
- ja pašreizējais elements ir lielāks par iepriekšējo, pievienojiet to curr_sum. Pretējā gadījumā atiestatiet curr_sum uz pašreizējo elementu.
- Ja curr_sum ir lielāks par max_sum, atjauniniet max_sum.
- Pēc cilpas max_sum saturēs lielāko blakusesošo pieaugošo apakšgrupu.
#include
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) } }
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)
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 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
Izvade
12
Laika sarežģītība: O(n).
Telpas sarežģītība: O(1).