Encuentre el subarreglo estrictamente creciente de la suma máxima

Dada una array de enteros positivos. Encuentre la suma máxima de subarreglos estrictamente crecientes. Tenga en cuenta que este problema es diferente de la suma máxima de subarreglo y los problemas de subsecuencia creciente de suma máxima .

Ejemplos: 

Entrada: arr[] = {1, 2, 3, 2, 5, 1, 7}
Salida: 8
Explicación:  algunos subarreglos estrictamente crecientes son 
{1, 2, 3} suma = 6, 
{2, 5} suma = 7 , 
{1, 7} suma 8 
Suma máxima = 8 

Entrada: arr[] = {1, 2, 2, 4}
Salida: 6
Explicación: el subarreglo creciente con suma máxima es 6.

Una solución simple es generar todos los subarreglos posibles y, para cada subarreglo, verificar si el subarreglo es estrictamente creciente o no. Si el subarreglo es estrictamente creciente, entonces calculamos la suma y actualizamos max_sum. Complejidad temporal O(n ² ).

Una solución eficiente de este problema toma O(n) tiempo. La idea es realizar un seguimiento de la suma máxima y la suma actual. Para cada elemento arr[i], si es mayor que arr[i-1], lo sumamos a la suma actual. De lo contrario, arr[i] es el punto de partida de otro posible candidato para el subarreglo creciente de suma máxima, por lo que actualizamos la suma actual como array. Pero antes de actualizar la suma actual, actualizamos la suma máxima si es necesario.

Let input array be 'arr[]' and size of array be 'n'

Initialize : 
max_sum = arr[0]
  // because if array size is 1 than it
  // would return that element.
  // used to store the maximum sum 
current_sum = arr[0] // used to compute current sum 

// Traverse array starting from second element
i goes from 1 to n-1

    // Check if it is strictly increasing then we 
    // update current_sum.
    current_sum = current_sum + arr[i]
    max_sum = max(max_sum, current_sum)
    // Also needed for subarray having last element.
    // else strictly increasing subarray breaks and 
    // arr[i] is starting point of next potential
    // subarray
    max_sum = max(max_sum, current_sum)
    current_sum = arr[i]

return max(max_sum, current_sum)    

A continuación se muestra la implementación de la idea anterior. 

// C/C++ program to find the maximum sum of strictly
// increasing subarrays
#include <iostream>
using namespace std;
 
// Returns maximum sum of strictly increasing
// subarrays
int maxsum_SIS(int arr[], int n)
{
    // Initialize max_sum be 0
    int max_sum = arr[0];
 
    // Initialize current sum be arr[0]
    int current_sum = arr[0];
 
    // Traverse array elements after first element.
    for (int i = 1; i < n; i++)
    {
        // update current_sum for
        // strictly increasing subarray
        if (arr[i - 1] < arr[i])
        {
            current_sum = current_sum + arr[i];
            max_sum = max(max_sum, current_sum);
        }
 
        else // strictly increasing subarray break
        {
            // update max_sum and current_sum ;
            max_sum = max(max_sum, current_sum);
            current_sum = arr[i];
        }
    }
 
    return max(max_sum, current_sum);
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << "Maximum sum : " << maxsum_SIS(arr, n);
    return 0;
}

// Java program to find the
// maximum sum of strictly increasing subarrays
 
public class GFG {
 
    // Returns maximum sum
    // of strictly increasing subarrays
    static int maxsum_SIS(int arr[], int n)
    {
        // Initialize max_sum be 0
        int max_sum = arr[0];
 
        // Initialize current sum be arr[0]
        int current_sum = arr[0];
 
        // Traverse array elements after first element.
        for (int i = 1; i < n; i++)
        {
            // update current_sum
            // for strictly increasing subarray
            if (arr[i - 1] < arr[i])
            {
                current_sum = current_sum + arr[i];
                max_sum = Math.max(max_sum, current_sum);
            }
            else // strictly increasing subarray break
            {
                // update max_sum and current_sum ;
                max_sum = Math.max(max_sum, current_sum);
                current_sum = arr[i];
            }
        }
 
        return Math.max(max_sum, current_sum);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 2, 4 };
        int n = arr.length;
        System.out.println("Maximum sum : "
                           + maxsum_SIS(arr, n));
    }
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find the maximum sum of strictly
# increasing subarrays
 
# Returns maximum sum of strictly increasing
# subarrays
 
 
def maxsum_SIS(arr, n):
    # Initialize max_sum be 0
    max_sum = arr[0]
 
    # Initialize current sum be arr[0]
    current_sum = arr[0]
 
    # Traverse array elements after first element.
    for i in range(1, n):
        # update current_sum for strictly increasing subarray
        if (arr[i-1] < arr[i]):
            current_sum = current_sum + arr[i]
            max_sum = max(max_sum, current_sum)
 
        else:
            # strictly increasing subarray break
            # update max_sum and current_sum
            max_sum = max(max_sum, current_sum)
            current_sum = arr[i]
 
    return max(max_sum, current_sum)
 
# Driver code
 
def main():
    arr = [1, 2, 2, 4]
    n = len(arr)
 
    print("Maximum sum : ", maxsum_SIS(arr, n)),
 
 
if __name__ == '__main__':
    main()
 
# This code is contributed by 29AjayKumar

// C# program to find the maximum sum of strictly
// increasing subarrays
using System;
public class GFG {
 
    // Returns maximum sum of strictly increasing
    // subarrays
    static int maxsum_SIS(int[] arr, int n)
    {
        // Initialize max_sum be 0
        int max_sum = arr[0];
 
        // Initialize current sum be arr[0]
        int current_sum = arr[0];
 
        // Traverse array elements after first element.
        for (int i = 1; i < n; i++) {
            // update current_sum for strictly increasing
            // subarray
            if (arr[i - 1] < arr[i]) {
                current_sum = current_sum + arr[i];
                max_sum = Math.Max(max_sum, current_sum);
            }
            else // strictly increasing subarray break
            {
                // update max_sum and current_sum ;
                max_sum = Math.Max(max_sum, current_sum);
                current_sum = arr[i];
            }
        }
 
        return Math.Max(max_sum, current_sum);
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 2, 2, 4 };
        int n = arr.Length;
        Console.WriteLine("Maximum sum : "
                          + maxsum_SIS(arr, n));
    }
}
 
// This code is contributed by 29AjayKumar

<?php
// PHP program to find the maximum sum of
// strictly increasing subarrays
 
// Returns maximum sum of strictly
// increasing subarrays
function maxsum_SIS($arr , $n)
{
    // Initialize max_sum be 0
    $max_sum = $arr[0];
 
    // Initialize current sum be arr[0]
    $current_sum = $arr[0];
 
    // Traverse array elements after
    // first element.
    for ($i = 1; $i < $n ; $i++)
    {
        // update current_sum for strictly
        // increasing subarray
        if ($arr[$i - 1] < $arr[$i]){
            $current_sum = $current_sum + $arr[$i];
            $max_sum = max($max_sum, $current_sum);
    }
 
        else // strictly increasing
             // subarray break
        {
            // update max_sum and current_sum ;
            $max_sum = max($max_sum, $current_sum);
            $current_sum = $arr[$i];
        }
    }
 
    return max($max_sum, $current_sum);
}
 
// Driver Code
$arr = array(1, 2, 2, 4);
$n = sizeof($arr);
 
echo "Maximum sum : ",
      maxsum_SIS($arr , $n);
 
// This code is contributed by Sachin
?>

<script>
 
// Javascript program to find the maximum sum of strictly
// increasing subarrays
 
// Returns maximum sum of strictly increasing
// subarrays
function maxsum_SIS(arr, n)
{
    // Initialize max_sum be 0
    var max_sum = arr[0];
 
    // Initialize current sum be arr[0]
    var current_sum = arr[0];
 
    // Traverse array elements after first element.
    for (var i = 1; i < n; i++)
    {
        // update current_sum for
        // strictly increasing subarray
        if (arr[i - 1] < arr[i])
        {
            current_sum = current_sum + arr[i];
            max_sum = Math.max(max_sum, current_sum);
        }
 
        else // strictly increasing subarray break
        {
            // update max_sum and current_sum ;
            max_sum = Math.max(max_sum, current_sum);
            current_sum = arr[i];
        }
    }
 
    return Math.max(max_sum, current_sum);
}
 
// Driver code
var arr = [ 1, 2, 2, 4 ];
var n = arr.length;
document.write( "Maximum sum : " + maxsum_SIS(arr, n));
 
// This code is contributed by itsok.
</script>

Maximum sum : 6

Complejidad temporal : O(n) 
Espacio auxiliar : O(1)

Este artículo es una contribución de Nishant_Singh (Pintu) y editado por Samraj Singh Solanki (kunwar_samraj_singh). 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.