Dots masīvs arr[] izmēra N . Uzdevums ir atrast blakus esošā apakšgrupas summu a robežās arr[] ar lielāko summu.

Piemērs:

Ievade: arr = {-2,-3,4,-1,-2,1,5,-3}
Izvade: 7
Paskaidrojums: Apakšplānā {4,-1, -2, 1, 5} ir lielākā summa 7.

Ievade: arr = {2}
Izvade: 2
Paskaidrojums: Apakšplūsmā {2} ir lielākā summa 1.

Ievade: arr = {5,4,1,7,8}
Izvade: 25
Paskaidrojums: Apakšplānā {5,4,1,7,8} ir lielākā summa 25.

Ideja par Kadanes algoritms ir saglabāt mainīgo max_beigas_šeit kas saglabā maksimālo blakus esošo apakšgrupu summu, kas beidzas ar pašreizējo indeksu un mainīgo max_so_far saglabā līdz šim atrasto blakus esošo apakšgrupu maksimālo summu, katru reizi, kad ir pozitīva summas vērtība max_beigas_šeit salīdziniet to ar max_so_far un atjaunināt max_so_far ja tas ir lielāks par max_so_far .

Tātad galvenais Intuīcija aiz muguras Kadanes algoritms ir,

• Apakšbloks ar negatīvu summu tiek atmests ( kodā piešķirot max_ending_here = 0 ).
• Mēs veicam apakšgrupu, līdz tā dod pozitīvu summu.

Kadanes algoritma pseidokods:

Palaist:
max_so_far = INT_MIN
max_beigas_šeit = 0

Cilpa katram masīva elementam

(a) max_beigas_šeit = max_beigas_šeit + a[i]
(b) if(max_so_far
max_so_far = max_beigas_šeit
(c) if(maks._beigas_šeit <0)
max_beigas_šeit = 0
atgriezties max_so_far

Kadanes algoritma ilustrācija:

Ņemsim piemēru: {-2, -3, 4, -1, -2, 1, 5, -3}

Piezīme : attēlā max_so_far ir attēlots ar Max_Sum un max_ending_here by Curr_Sum

Ja i=0, a[0] = -2

pirmais klēpjdators

• max_beigas_šeit = max_beigas_šeit + (-2)
• Iestatīt max_ending_here = 0, jo max_ending_here <0
• un iestatiet max_so_far = -2

Ja i=1, a[1] = -3

• max_beigas_šeit = max_beigas_šeit + (-3)
• Tā kā max_ending_here = -3 un max_so_far = -2, max_so_far paliks -2
• Iestatīt max_ending_here = 0, jo max_ending_here <0

Ja i=2, a[2] = 4

• max_beigas_šeit = max_beigas_šeit + (4)
• max_beigas_šeit = 4
• max_so_far ir atjaunināts uz 4, jo max_ending_here ir lielāks par max_so_far, kas līdz šim bija -2

Ja i=3, a[3] = -1

pārveidot virkni par int

• max_beigas_šeit = max_beigas_šeit + (-1)
• max_ending_here = 3

Ja i=4, a[4] = -2

• max_beigas_šeit = max_beigas_šeit + (-2)
• max_ending_here = 1

Ja i=5, a[5] = 1

• max_beigas_šeit = max_beigas_šeit + (1)
• max_beigas_šeit = 2

Ja i=6, a[6] = 5

• max_beigas_šeit = max_beigas_šeit + (5)
• max_ending_here =
• max_so_far ir atjaunināts uz 7, jo max_ending_here ir lielāks par max_so_far

Ja i=7, a[7] = -3

• max_beigas_šeit = max_beigas_šeit + (-3)
• max_beigas_šeit = 4

Lai īstenotu ideju, veiciet tālāk norādītās darbības.

• Inicializējiet mainīgos max_so_far = INT_MIN un max_beigas_šeit = 0
• Palaist for cilpu no 0 uz N-1 un katram indeksam i :
  • Pievienojiet arr[i] uz max_ending_here.
  • Ja max_so_far ir mazāks par max_ending_here, atjauniniet max_so_far to max_ending_here .
  • Ja max_beigas_šeit <0, atjauniniet max_beigas_šeit = 0
• Atgriezt max_so_far

Zemāk ir aprakstīta iepriekš minētās pieejas īstenošana.

// C++ program to print largest contiguous array sum #include  using namespace std; int maxSubArraySum(int a[], int size) {  int max_so_far = INT_MIN, max_ending_here = 0;  for (int i = 0; i < size; i++) {  max_ending_here = max_ending_here + a[i];  if (max_so_far < max_ending_here)  max_so_far = max_ending_here;  if (max_ending_here < 0)  max_ending_here = 0;  }  return max_so_far; } // Driver Code int main() {  int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };  int n = sizeof(a) / sizeof(a[0]);  // Function Call  int max_sum = maxSubArraySum(a, n);  cout << 'Maximum contiguous sum is ' << max_sum;  return 0; }>

// Java program to print largest contiguous array sum import java.io.*; import java.util.*; class Kadane {  // Driver Code  public static void main(String[] args)  {  int[] a = { -2, -3, 4, -1, -2, 1, 5, -3 };  System.out.println('Maximum contiguous sum is '  + maxSubArraySum(a));  }  // Function Call  static int maxSubArraySum(int a[])  {  int size = a.length;  int max_so_far = Integer.MIN_VALUE, max_ending_here  = 0;  for (int i = 0; i < size; i++) {  max_ending_here = max_ending_here + a[i];  if (max_so_far < max_ending_here)  max_so_far = max_ending_here;  if (max_ending_here < 0)  max_ending_here = 0;  }  return max_so_far;  } }>

def GFG(a, size): max_so_far = float('-inf') # Use float('-inf') instead of maxint max_ending_here = 0 for i in range(0, size): max_ending_here = max_ending_here + a[i] if max_so_far < max_ending_here: max_so_far = max_ending_here if max_ending_here < 0: max_ending_here = 0 return max_so_far # Driver function to check the above function a = [-2, -3, 4, -1, -2, 1, 5, -3] print('Maximum contiguous sum is', GFG(a, len(a)))>

// C# program to print largest // contiguous array sum using System; class GFG {  static int maxSubArraySum(int[] a)  {  int size = a.Length;  int max_so_far = int.MinValue, max_ending_here = 0;  for (int i = 0; i < size; i++) {  max_ending_here = max_ending_here + a[i];  if (max_so_far < max_ending_here)  max_so_far = max_ending_here;  if (max_ending_here < 0)  max_ending_here = 0;  }  return max_so_far;  }  // Driver code  public static void Main()  {  int[] a = { -2, -3, 4, -1, -2, 1, 5, -3 };  Console.Write('Maximum contiguous sum is '  + maxSubArraySum(a));  } } // This code is contributed by Sam007_>

>>PHP>>  
  Izvade  
Maximum contiguous sum is 7>
  
    Laika sarežģītība:    O(N)  
    Palīgtelpa:    O(1)
 
Drukāt lielākās summas blakus esošo apakšrindu:
 
Lai izdrukātu apakšgrupu ar maksimālo summu, ideja ir saglabāt    sākt    indekss no    maksimālā_summa_beidzas_šeit    pie pašreizējā indeksa, lai vienmēr    maksimālā_summa_līdz šim    ir atjaunināts ar    maksimālā_summa_beidzas_šeit    tad apakšgrupas sākuma indeksu un beigu indeksu var atjaunināt ar    sākt    un    pašreizējais indekss    .
 
Lai īstenotu ideju, veiciet tālāk norādītās darbības.
 
Inicializējiet mainīgos    s    ,    sākt,    un    beigas    ar    0    un    max_so_far    = INT_MIN un    max_beigas_šeit    = 0
Palaist for cilpu no    0    uz    N-1    un katram indeksam    i    :
Pievienojiet arr[i]         uz max_ending_here.
Ja max_so_far ir mazāks par max_ending_here, atjauniniet         max_so_far uz max_ending_šeit un atjauniniet    sākt    uz    s    un    beigas    uz    i    .
Ja max_ending_here <0, tad atjauniniet max_ending_here = 0 un    s    ar    i+1    .
Drukājiet vērtības no indeksa    sākt    uz    beigas    .
Zemāk ir aprakstīta iepriekš minētās pieejas īstenošana:
C++ 
// C++ program to print largest contiguous array sum #include  #include  using namespace std; void maxSubArraySum(int a[], int size) {  int max_so_far = INT_MIN, max_ending_here = 0,  start = 0, end = 0, s = 0;  for (int i = 0; i < size; i++) {  max_ending_here += a[i];  if (max_so_far < max_ending_here) {  max_so_far = max_ending_here;  start = s;  end = i;  }  if (max_ending_here < 0) {  max_ending_here = 0;  s = i + 1;  }  }  cout << 'Maximum contiguous sum is ' << max_so_far  << endl;  cout << 'Starting index ' << start << endl  << 'Ending index ' << end << endl; } /*Driver program to test maxSubArraySum*/ int main() {  int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };  int n = sizeof(a) / sizeof(a[0]);  maxSubArraySum(a, n);  return 0; }>
 Java 
// Java program to print largest // contiguous array sum import java.io.*; import java.util.*; class GFG {  static void maxSubArraySum(int a[], int size)  {  int max_so_far = Integer.MIN_VALUE,  max_ending_here = 0, start = 0, end = 0, s = 0;  for (int i = 0; i < size; i++) {  max_ending_here += a[i];  if (max_so_far < max_ending_here) {  max_so_far = max_ending_here;  start = s;  end = i;  }  if (max_ending_here < 0) {  max_ending_here = 0;  s = i + 1;  }  }  System.out.println('Maximum contiguous sum is '  + max_so_far);  System.out.println('Starting index ' + start);  System.out.println('Ending index ' + end);  }  // Driver code  public static void main(String[] args)  {  int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };  int n = a.length;  maxSubArraySum(a, n);  } } // This code is contributed by prerna saini>
 Python 
# Python program to print largest contiguous array sum from sys import maxsize # Function to find the maximum contiguous subarray # and print its starting and end index def maxSubArraySum(a, size): max_so_far = -maxsize - 1 max_ending_here = 0 start = 0 end = 0 s = 0 for i in range(0, size): max_ending_here += a[i] if max_so_far < max_ending_here: max_so_far = max_ending_here start = s end = i if max_ending_here < 0: max_ending_here = 0 s = i+1 print('Maximum contiguous sum is %d' % (max_so_far)) print('Starting Index %d' % (start)) print('Ending Index %d' % (end)) # Driver program to test maxSubArraySum a = [-2, -3, 4, -1, -2, 1, 5, -3] maxSubArraySum(a, len(a))>
 C# 
// C# program to print largest // contiguous array sum using System; class GFG {  static void maxSubArraySum(int[] a, int size)  {  int max_so_far = int.MinValue, max_ending_here = 0,  start = 0, end = 0, s = 0;  for (int i = 0; i < size; i++) {  max_ending_here += a[i];  if (max_so_far < max_ending_here) {  max_so_far = max_ending_here;  start = s;  end = i;  }  if (max_ending_here < 0) {  max_ending_here = 0;  s = i + 1;  }  }  Console.WriteLine('Maximum contiguous '  + 'sum is ' + max_so_far);  Console.WriteLine('Starting index ' + start);  Console.WriteLine('Ending index ' + end);  }  // Driver code  public static void Main()  {  int[] a = { -2, -3, 4, -1, -2, 1, 5, -3 };  int n = a.Length;  maxSubArraySum(a, n);  } } // This code is contributed // by anuj_67.>
 Javascript 
>>PHP>>  
  Izvade      Laika sarežģītība:    O(n)  
    Palīgtelpa:    O(1)
 
Lielākā summa blakus esošā apakšgrupa, izmantojot Dinamiskā programmēšana :
 
Katram indeksam i DP[i] saglabā maksimāli iespējamo lielāko kopējo blakus esošo apakšrindu, kas beidzas ar indeksu i, un tāpēc mēs varam aprēķināt DP[i], izmantojot minēto stāvokļa pāreju:
 
DP[i] = maks (DP[i-1] + arr[i], arr[i])
Tālāk ir norādīta ieviešana:
C++ 
// C++ program to print largest contiguous array sum #include  using namespace std; void maxSubArraySum(int a[], int size) {  vector dp(izmērs, 0);  dp[0] = a[0];  int ans = dp[0];  for (int i = 1; i< size; i++) {  dp[i] = max(a[i], a[i] + dp[i - 1]);  ans = max(ans, dp[i]);  }  cout << ans; } /*Driver program to test maxSubArraySum*/ int main() {  int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };  int n = sizeof(a) / sizeof(a[0]);  maxSubArraySum(a, n);  return 0; }>
 Java 
import java.util.Arrays; public class Main {  // Function to find the largest contiguous array sum  public static void maxSubArraySum(int[] a) {  int size = a.length;  int[] dp = new int[size]; // Create an array to store intermediate results  dp[0] = a[0]; // Initialize the first element of the intermediate array with the first element of the input array  int ans = dp[0]; // Initialize the answer with the first element of the intermediate array  for (int i = 1; i < size; i++) {  // Calculate the maximum of the current element and the sum of the current element and the previous result  dp[i] = Math.max(a[i], a[i] + dp[i - 1]);  // Update the answer with the maximum value encountered so far  ans = Math.max(ans, dp[i]);  }  // Print the maximum contiguous array sum  System.out.println(ans);  }  public static void main(String[] args) {  int[] a = { -2, -3, 4, -1, -2, 1, 5, -3 };  maxSubArraySum(a); // Call the function to find and print the maximum contiguous array sum  } } // This code is contributed by shivamgupta310570>
 Python 
# Python program for the above approach def max_sub_array_sum(a, size): # Create a list to store intermediate results dp = [0] * size # Initialize the first element of the list with the first element of the array dp[0] = a[0] # Initialize the answer with the first element of the array ans = dp[0] # Loop through the array starting from the second element for i in range(1, size): # Choose the maximum value between the current element and the sum of the current element # and the previous maximum sum (stored in dp[i - 1]) dp[i] = max(a[i], a[i] + dp[i - 1]) # Update the overall maximum sum ans = max(ans, dp[i]) # Print the maximum contiguous subarray sum print(ans) # Driver program to test max_sub_array_sum if __name__ == '__main__': # Sample array a = [-2, -3, 4, -1, -2, 1, 5, -3] # Get the length of the array n = len(a) # Call the function to find the maximum contiguous subarray sum max_sub_array_sum(a, n) # This code is contributed by Susobhan Akhuli>
 C# 
using System; class MaxSubArraySum {  // Function to find and print the maximum sum of a  // subarray  static void FindMaxSubArraySum(int[] arr, int size)  {  // Create an array to store the maximum sum of  // subarrays  int[] dp = new int[size];  // Initialize the first element of dp with the first  // element of arr  dp[0] = arr[0];  // Initialize a variable to store the final result  int ans = dp[0];  // Iterate through the array to find the maximum sum  for (int i = 1; i < size; i++) {  // Calculate the maximum sum ending at the  // current position  dp[i] = Math.Max(arr[i], arr[i] + dp[i - 1]);  // Update the final result with the maximum sum  // found so far  ans = Math.Max(ans, dp[i]);  }  // Print the maximum sum of the subarray  Console.WriteLine(ans);  }  // Driver program to test FindMaxSubArraySum  static void Main()  {  // Example array  int[] arr = { -2, -3, 4, -1, -2, 1, 5, -3 };  // Calculate and print the maximum subarray sum  FindMaxSubArraySum(arr, arr.Length);  } }>
 Javascript 
// Javascript program to print largest contiguous array sum // Function to find the largest contiguous array sum function maxSubArraySum(a) {  let size = a.length;  // Create an array to store intermediate results  let dp = new Array(size);  // Initialize the first element of the intermediate array with the first element of the input array  dp[0] = a[0];  // Initialize the answer with the first element of the intermediate array  let ans = dp[0];    for (let i = 1; i < size; i++) {  // Calculate the maximum of the current element and the sum of the current element and the previous result  dp[i] = Math.max(a[i], a[i] + dp[i - 1]);  // Update the answer with the maximum value encountered so far  ans = Math.max(ans, dp[i]);  }  // Print the maximum contiguous array sum  console.log(ans); } let a = [-2, -3, 4, -1, -2, 1, 5, -3]; // Call the function to find and print the maximum contiguous array sum maxSubArraySum(a);>
   
  Izvade    
    Prakses problēma:     
  
Ņemot vērā veselu skaitļu masīvu (iespējams, daži elementi ir negatīvi), uzrakstiet C programmu, lai noskaidrotu *maksimālo reizinājumu*, kas ir iespējams, reizinot “n” secīgus veselus skaitļus masīvā, kur n ? ARRAY_SIZE. Izdrukājiet arī maksimālā produkta apakšgrupas sākumpunktu.