최대 합계 연속 하위 배열(KADANE의 알고리즘) - TECHCODEVIEW.COM

배열이 주어지면 도착[] 크기의 N . 이 작업은 인접한 하위 배열의 합을 구하는 것입니다. 도착[] 가장 큰 금액으로.

예:

입력: 도착 = {-2,-3,4,-1,-2,1,5,-3}
산출: 7
설명: 하위 배열 {4,-1, -2, 1, 5}의 합이 가장 큰 값은 7입니다.

입력: 도착 = {2}
산출: 2
설명: 하위 배열 {2}의 합이 가장 큰 값은 1입니다.

입력: 도착 = {5,4,1,7,8}
산출: 25
설명: 하위 배열 {5,4,1,7,8}의 합이 가장 큰 값은 25입니다.

카다네 알고리즘

권장되는 문제 해결 문제

아이디어 Kadane의 알고리즘 변수를 유지하는 것입니다 최대_끝_여기 현재 인덱스에서 끝나는 연속 하위 배열의 최대 합계와 변수를 저장합니다. max_so_far 지금까지 발견된 연속 하위 배열의 최대 합을 저장합니다. 최대_끝_여기 그것과 비교하다 max_so_far 그리고 업데이트 max_so_far 보다 큰 경우 max_so_far .

그래서 주요 직관 뒤에 Kadane의 알고리즘 이다,

음수 합계가 있는 하위 배열은 삭제됩니다( 코드에서 max_ending_here = 0을 할당하여 ).
양의 합이 나올 때까지 하위 배열을 운반합니다.

Kadane 알고리즘의 의사 코드:

초기화:
max_so_far = INT_MIN
max_ending_here = 0

배열의 각 요소에 대한 루프

(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far
max_so_far = max_ending_here
(c) if(max_ending_here <0)
max_ending_here = 0
max_so_far 반환

Kadane의 알고리즘 예시:

예를 들어보겠습니다: {-2, -3, 4, -1, -2, 1, 5, -3}

메모 : 이미지에서 max_so_far는 다음과 같이 표시됩니다. 최대_합 그리고 max_ending_here by Curr_Sum

i=0인 경우 a[0] = -2
Arduino의 전송 속도

max_ending_here = max_ending_here + (-2)
max_ending_here <0이므로 max_ending_here = 0으로 설정하세요.
max_so_far = -2로 설정합니다.
i=1인 경우 a[1] = -3

max_ending_here = max_ending_here + (-3)
max_ending_here = -3 및 max_so_far = -2이므로 max_so_far는 -2로 유지됩니다.
max_ending_here <0이므로 max_ending_here = 0으로 설정하세요.
i=2인 경우 a[2] = 4

max_ending_here = max_ending_here + (4)
max_ending_here = 4
max_ending_here가 지금까지 -2였던 max_so_far보다 크기 때문에 max_so_far는 4로 업데이트됩니다.
i=3인 경우 a[3] = -1

max_ending_here = max_ending_here + (-1)
max_ending_here = 3
i=4인 경우 a[4] = -2

max_ending_here = max_ending_here + (-2)
max_ending_here = 1
i=5인 경우 a[5] = 1

max_ending_here = max_ending_here + (1)
max_ending_here = 2
i=6인 경우 a[6] = 5

max_ending_here = max_ending_here + (5)
max_ending_here=
max_ending_here가 max_so_far보다 크기 때문에 max_so_far는 7로 업데이트됩니다.
i=7인 경우 a[7] = -3

max_ending_here = max_ending_here + (-3)
max_ending_here = 4

아이디어를 구현하려면 아래 단계를 따르십시오.

변수 초기화 max_so_far = INT_MIN 및 최대_끝_여기 = 0
다음에서 for 루프를 실행하세요. 0 에게 N-1 그리고 각 인덱스에 대해 나 :
- arr[i] 추가 max_ending_here로.
- max_so_far가 max_ending_here보다 작으면 업데이트하세요. max_so_far에서 max_ending_here까지 .
- max_ending_here <0이면 max_ending_here = 0으로 업데이트하세요.
max_so_far 반환

다음은 위의 접근 방식을 구현한 것입니다.

C++

 // 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

  // PHP program to print largest // contiguous array sum function maxSubArraySum($a, $size) { $max_so_far = PHP_INT_MIN; $max_ending_here = 0; for ($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 $a = array(-2, -3, 4, -1, -2, 1, 5, -3); $n = count($a); $max_sum = maxSubArraySum($a, $n); echo 'Maximum contiguous sum is ' , $max_sum; // This code is contributed by anuj_67. ?>>

산출

Maximum contiguous sum is 7>

시간 복잡도: 에)
보조 공간: 오(1)

가장 큰 합계 연속 하위 배열을 인쇄합니다.

최대 합계로 하위 배열을 인쇄하려면 아이디어를 유지해야 합니다. 시작 색인 최대_합계_끝_여기 현재 인덱스에서 maximum_sum_so_far 으로 업데이트됩니다 최대_합계_끝_여기 그런 다음 하위 배열의 시작 인덱스와 끝 인덱스를 다음과 같이 업데이트할 수 있습니다. 시작 그리고 현재 지수 .

아이디어를 구현하려면 아래 단계를 따르십시오.

변수 초기화 에스 , 시작, 그리고 끝 ~와 함께 0 그리고 max_so_far = INT_MIN 및 최대_끝_여기 = 0
다음에서 for 루프를 실행하세요. 0 에게 N-1 그리고 각 인덱스에 대해 나 :
- arr[i] 추가 max_ending_here로.
- max_so_far가 max_ending_here보다 작으면 업데이트하세요. max_so_far에서 max_ending_here까지 업데이트 시작 에게 에스 그리고 끝 에게 나 .
- max_ending_here <0이면 max_ending_here = 0으로 업데이트하고 에스 ~와 함께 나+1 .
인덱스에서 값 인쇄 시작 에게 끝 .

다음은 위의 접근 방식을 구현한 것입니다.

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

자바스크립트

PHP

  // PHP program to print largest  // contiguous array sum function maxSubArraySum($a, $size) { $max_so_far = PHP_INT_MIN; $max_ending_here = 0; $start = 0; $end = 0; $s = 0; for ($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; } } echo 'Maximum contiguous sum is '. $max_so_far.'
'; echo 'Starting index '. $start . '
'. 'Ending index ' . $end . '
'; } // Driver Code $a = array(-2, -3, 4, -1, -2, 1, 5, -3); $n = sizeof($a); maxSubArraySum($a, $n); // This code is contributed // by ChitraNayal ?>>

산출

Maximum contiguous sum is 7 Starting index 2 Ending index 6>

시간 복잡도: 에)
보조 공간: 오(1)

다음을 사용한 최대 합계 연속 하위 배열 동적 프로그래밍 :

각 인덱스 i에 대해 DP[i]는 인덱스 i에서 끝나는 가능한 최대 합 연속 하위 배열을 저장하므로 언급된 상태 전환을 사용하여 DP[i]를 계산할 수 있습니다.

DP[i] = 최대(DP[i-1] + arr[i] , arr[i] )

구현은 다음과 같습니다.

C++

 // C++ program to print largest contiguous array sum #include  using namespace std; void maxSubArraySum(int a[], int size) {  vector dp(크기, 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; }>

자바

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

씨#

 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 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);>

산출

7>

연습 문제:

파이썬 튜플 정렬

정수 배열(아마도 일부 음수 요소)이 주어지면 배열에서 'n'개의 연속 정수를 곱하여 가능한 *최대 곱*을 찾는 C 프로그램을 작성하세요. 여기서 n ? ARRAY_SIZE. 또한 최대 제품 하위 배열의 시작점을 인쇄합니다.

TechCodeview

최대 합계 연속 하위 배열(Kadane 알고리즘)

Kadane 알고리즘의 의사 코드:

Kadane의 알고리즘 예시:

가장 큰 합계 연속 하위 배열을 인쇄합니다.

다음을 사용한 최대 합계 연속 하위 배열 동적 프로그래밍 :