Suma máxima obtenida al dividir Array en varios subarreglos según las condiciones dadas

Dado un arreglo arr[] de tamaño N , la tarea es calcular la suma máxima que se puede obtener al dividir el arreglo en varios subarreglos ( posiblemente uno), donde cada subarreglo comienza en el índice i y termina en el índice j (j>= i) contribuye arr[j]-arr[i] a la suma.

Ejemplos:

Entrada: arr[]= {1, 5, 3}, N=3
Salida: 
4
Explicación : la array se puede dividir en 2 subarreglos:

• {1, 5} -> suma aportada por el subarreglo = 5-1 = 4
• {3} -> suma aportada por el subarreglo = 3-3 = 0

Por lo tanto, la respuesta es 4. (Se puede demostrar que no hay otra forma de dividir esta array en múltiples subarreglos de modo que la respuesta sea mayor que 4).

Entrada: arr[] = {6, 2, 1}, N=3
Salida:
0

Enfoque ingenuo: el enfoque ingenuo es considerar todas las formas posibles de dividir arr en 1 o más subarreglos y calcular la suma máxima obtenida para cada uno.

Complejidad temporal: O(N*2 ^N )
Espacio auxiliar: O(1)

Observación: Las observaciones necesarias para resolver el problema son las siguientes:

1. La array debe dividirse en varios (posiblemente uno) subarreglos de modo que cada subarreglo sea el subarreglo de mayor crecimiento . Por ejemplo, si arr[]={3,5,7,9,1} , es óptimo considerar {3,5,7,9} como un subarreglo, ya que contribuiría 9-3=6 a la suma. Dividirlo aún más disminuye la suma que no es óptima.
2. Todos los elementos de un subarreglo no creciente deben considerarse como subarreglos de un solo elemento para que contribuyan con 0 a la suma. De lo contrario, estarían aportando un valor negativo. Por ejemplo, si arr[i]>arr[i+1], es óptimo considerar dos subarreglos de longitud 1 que contengan arr[i] y arr[i+1] por separado, de modo que contribuyan (arr[i]- arr[i]) +(arr[i+1]-arr[i+1]) =0 a la respuesta. Si se consideraran juntos, aportarían arr[i+1]-arr[i] que es un número negativo, disminuyendo así la suma.

Enfoque eficiente: siga los pasos a continuación para resolver el problema:

1. Inicializa una variable Sum a 0.
2. Recorra arr de 1 a N-1, usando la variable i , y haga lo siguiente:
   1. Si arr[i]>arr[i-1] , agregue arr[i]-arr[i-1] a Sum . Esto funciona porque la suma de las diferencias de los elementos adyacentes en una array ordenada es igual a la diferencia de los elementos en los extremos. Aquí, solo los subarreglos crecientes se consideran como arr[i]>arr[i-1].

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required answer
int maximumSum(int arr[], int N)
{
    // Stores maximum sum
    int Sum = 0;
    for (int i = 1; i < N; i++) {
 
        // Adding the difference of elements at ends of
        // increasing subarray to the answer
        if (arr[i] > arr[i - 1])
            Sum += (arr[i] - arr[i - 1]);
    }
    return Sum;
}
// Driver Code
int main()
{
    // Input
    int arr[] = { 1, 5, 3 };
    int N = (sizeof(arr) / (sizeof(arr[0])));
 
    // Function calling
    cout << maximumSum(arr, N);
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to find the required answer
public static int maximumSum(int arr[], int N)
{
     
    // Stores maximum sum
    int Sum = 0;
    for(int i = 1; i < N; i++)
    {
         
        // Adding the difference of elements at ends
        // of increasing subarray to the answer
        if (arr[i] > arr[i - 1])
            Sum += (arr[i] - arr[i - 1]);
    }
    return Sum;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Input
    int arr[] = { 1, 5, 3 };
    int N = arr.length;
 
    // Function calling
    System.out.println(maximumSum(arr, N));
}
}
 
// This code is contributed by Potta Lokesh

# Python program for the above approach
 
# Function to find the required answer
def maximumSum(arr, N):
   
    # Stores maximum sum
    Sum = 0;
    for i in range(1,N):
       
        # Adding the difference of elements at ends of
        # increasing subarray to the answer
        if (arr[i] > arr[i - 1]):
            Sum += (arr[i] - arr[i - 1])
     
    return Sum;
     
# Driver Code
 
#Input
arr = [ 1, 5, 3 ];
N = len(arr)
 
# Function calling
print(maximumSum(arr, N));
 
# This code is contributed by SoumikMondal

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the required answer
static int maximumSum(int []arr, int N)
{
     
    // Stores maximum sum
    int Sum = 0;
    for(int i = 1; i < N; i++)
    {
         
        // Adding the difference of elements at
        // ends of increasing subarray to the answer
        if (arr[i] > arr[i - 1])
            Sum += (arr[i] - arr[i - 1]);
    }
    return Sum;
}
 
// Driver Code
public static void Main()
{
     
    // Input
    int []arr = { 1, 5, 3 };
    int N = arr.Length;
 
    // Function calling
    Console.Write(maximumSum(arr, N));
}
}
 
// This code is contributed by SURENDRA_GANGWAR

<script>
 
// JavaScript program for the above approach
 
// Function to find the required answer
function maximumSum(arr, N)
{
     
    // Stores maximum sum
    let Sum = 0;
    for(let i = 1; i < N; i++)
    {
         
        // Adding the difference of elements at ends
        // of increasing subarray to the answer
        if (arr[i] > arr[i - 1])
            Sum += (arr[i] - arr[i - 1]);
    }
    return Sum;
}
 
// Driver Code
 
// Input
let arr = [ 1, 5, 3 ];
let N = arr.length;
 
// Function calling
document.write(maximumSum(arr, N));
 
// This code is contributed by Potta Lokesh
 
</script>

4

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