logo

TechCodeview

連続して増加する部分配列の最大合計

GfG Practice で試してみる ' title= #practiceLinkDiv { 表示: なし !重要; }

n 個の正の個別の整数の配列が与えられます。問題は、連続的に増加する部分配列の最大の合計を O(n) 時間の計算量で見つけることです。

Javaフォーマット文字列

例:  

    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 貪欲なフォックス 試してみてください!

あ 簡単な解決策 することです すべての部分配列を生成する そしてそれらの合計を計算します。最後に、最大合計を持つ部分配列を返します。このソリューションの時間計算量は 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

以下は上記のアルゴリズムの実装です。

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

出力 
Largest sum = 12

時間計算量 : O(n)

 

連続して増加する部分配列の最大合計値 再帰 : 

この問題を解決するための再帰アルゴリズム:

この問題の段階的なアルゴリズムは次のとおりです。

  1. 機能 '最大合計' 配列を受け取ります 「アー」 そしてそのサイズは 「ん」。
  2. もし   「n==1」 それから戻ります 到着[0]回目 要素。
  3. もし 「n != 1」 次に関数を再帰的に呼び出します '最大合計'   部分配列の最大の合計を見つけるには 'arr[0...n-1]' 最後の要素を除く 'arr[n-1]' 。
  4.  最後から 2 番目の要素から逆の順序で配列を反復処理することにより、次で終わる増加する部分配列の合計を計算します。 'arr[n-1]' 。 1 つの要素が次の要素より小さい場合は、現在の合計に追加する必要があります。それ以外の場合は、ループを切断する必要があります。
  5. 次に、最大合計の最大値を返します。つまり、 ' return max(max_sum curr_sum);' 。
     

上記のアルゴリズムの実装は次のとおりです。

C++ 
#include    using namespace std; // Recursive function to find the largest sum // of contiguous increasing subarray int largestSum(int arr[] int n) {  // Base case  if (n == 1)  return arr[0];  // Recursive call to find the largest sum  int max_sum = 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 max(max_sum curr_sum); } // 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; } // This code is contributed by Vaibhav Saroj.
C 
#include  #include  // 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]);  printf('Largest sum = %dn' largestSum(arr n));  return 0; } // This code is contributed by Vaibhav Saroj.
Java 
/*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.
Python 
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# 
// 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
JavaScript 
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));
PHP 
 // 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

時間計算量: O(n^2)。
空間の複雑さ: の上）。

Kadane のアルゴリズムを使用した最大合計連続増加部分配列:-

最大の合計部分配列を取得するには、Kadane のアプローチが使用されますが、配列には正と負の両方の値が含まれることが前提となります。この例では、連続して上昇する部分配列でのみ機能するようにアルゴリズムを変更する必要があります。

以下は、連続して増加する部分配列の最大合計を見つけるために Kadane のアルゴリズムを変更する方法です。

  1. 2 つの変数 max_sum と curr_sum を配列の最初の要素に初期化します。
  2. 2 番目の要素から開始して配列をループします。
  3. 現在の要素が前の要素より大きい場合は、それを curr_sum に追加します。それ以外の場合は、curr_sum を現在の要素にリセットします。
  4. curr_sum が max_sum より大きい場合は、max_sum を更新します。
  5. ループの後、max_sum には連続して増加するサブ配列の最大合計が含まれます。
     
C++ 
#include    using namespace std; int largest_sum_contiguous_increasing_subarray(int arr[] int n) {  int max_sum = arr[0];  int curr_sum = arr[0];  for (int i = 1; i < n; i++) {  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; } int main() {  int arr[] = { 1 1 4 7 3 6 };  int n = sizeof(arr)/sizeof(arr[0]);  cout << largest_sum_contiguous_increasing_subarray(arr n) << endl; // Output: 44 (1+2+3+5+7+8+9+10)  return 0; }
Java 
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)  } }
Python3 
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)
C# 
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 
 // 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)。

クイズの作成