#practiceLinkDiv { 표시: 없음 !중요; }n개의 양의 고유 정수 배열이 주어졌습니다. 문제는 O(n) 시간 복잡도에서 연속적으로 증가하는 하위 배열의 최대 합을 찾는 것입니다.
예:
Input : arr[] = {2 1 4 7 3 6}Recommended Practice 탐욕스러운 여우 시도해 보세요!
Output : 12
Contiguous Increasing subarray {1 4 7} = 12
Input : arr[] = {38 7 8 10 12}
Output : 38
에이 간단한 해결책 이다 모든 하위 배열 생성 그리고 그 합계를 계산합니다. 마지막으로 최대 합계를 갖는 하위 배열을 반환합니다. 이 솔루션의 시간 복잡도는 O(n2).
클러스터링
안 효율적인 솔루션 모든 요소가 긍정적이라는 사실에 기초합니다. 따라서 가장 오래 증가하는 하위 배열을 고려하고 그 합을 비교합니다. 하위 배열을 늘리면 겹칠 수 없으므로 시간 복잡도는 O(n)이 됩니다.
연산:
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
아래는 위의 알고리즘을 구현한 것입니다.
10억은 몇 백만인가요?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. ?> 산출
Largest sum = 12
시간복잡도 : O(n)
연속적으로 증가하는 부분 배열의 최대 합 재귀 :
이 문제를 해결하기 위한 재귀 알고리즘:
문제의 단계별 알고리즘은 다음과 같습니다.
- 기능 '가장 큰 합계' 배열을 취함 '아르' 그리고 그 크기는 'N'.
- 만약에 'n==1' 그런 다음 돌아오다 도착[0]번째 요소.
- 만약에 'n != 1' 그런 다음 재귀적으로 함수를 호출합니다. '가장 큰 합계' 하위 배열의 가장 큰 합을 찾으려면 'arr[0...n-1]' 마지막 요소 제외 'arr[n-1]' .
- 두 번째 마지막 요소부터 시작하여 역순으로 배열을 반복하여 다음에서 끝나는 증가하는 하위 배열의 합계를 계산합니다. 'arr[n-1]' . 한 요소가 다음 요소보다 작으면 현재 합계에 추가해야 합니다. 그렇지 않으면 루프가 깨져야 합니다.
- 그런 다음 가장 큰 합계의 최대값을 반환합니다. ' 최대값(max_sum curr_sum)을 반환합니다.' .
위 알고리즘의 구현은 다음과 같습니다.
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); ?> 산출
Largest sum = 12
시간 복잡도: 오(n^2).
공간 복잡도: 에).
Kadane 알고리즘을 사용한 최대 합계 연속 증가 하위 배열:-
가장 큰 합계 하위 배열을 얻으려면 Kadane의 접근 방식이 사용되지만 배열에 양수 값과 음수 값이 모두 포함되어 있다고 가정합니다. 이 경우 연속적으로 상승하는 하위 배열에서만 작동하도록 알고리즘을 변경해야 합니다.
다음은 Kadane의 알고리즘을 수정하여 연속 증가 부분 배열의 최대 합계를 찾는 방법입니다.
- 두 개의 변수 max_sum 및 curr_sum을 배열의 첫 번째 요소로 초기화합니다.
- 두 번째 요소부터 시작하여 배열을 반복합니다.
- 현재 요소가 이전 요소보다 크면 curr_sum에 추가합니다. 그렇지 않으면 curr_sum을 현재 요소로 재설정합니다.
- curr_sum이 max_sum보다 크면 max_sum을 업데이트하세요.
- 루프 후에 max_sum은 연속적으로 증가하는 하위 배열의 가장 큰 합계를 포함합니다.
#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
산출
12
시간 복잡도: O(n).
공간 복잡도: O(1).
자바 배열 정렬퀴즈 만들기