Subarreglo creciente contiguo de suma más grande

Dada una array de n enteros positivos distintos. El problema es encontrar la mayor suma de subarreglo creciente contiguo en complejidad de tiempo O(n).

Ejemplos: 

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

Una solución simple es generar todos los subarreglos y calcular sus sumas. Finalmente devuelva el subarreglo con suma máxima. La complejidad temporal de esta solución es O(n 2 ).

Una solución eficiente se basa en el hecho de que todos los elementos son positivos. Así que consideramos los subarreglos crecientes más largos y comparamos sus sumas. Para aumentar los subarreglos no se pueden superponer, por lo que nuestra complejidad de tiempo se convierte en O (n).

Algoritmo: 

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

A continuación se muestra la implementación del algoritmo anterior.

C++

// C++ implementation of largest sum
// contiguous increasing subarray
#include <bits/stdc++.h>
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.

PHP

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

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>
Producción

Largest sum = 12

Complejidad de tiempo : O(n)

Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *