Dada una array arr[] que consta de N enteros, la tarea es encontrar la suma de las diferencias entre el elemento máximo y mínimo de todos los subarreglos estrictamente crecientes de la array dada. Todos los subarreglos deben estar en su forma más larga posible, es decir, si un subarreglo [i, j] forma un subarreglo estrictamente creciente, entonces debe considerarse como un todo y no [i, k] y [k+1, j] para algunos i <= k <= j.
Se dice que un subarreglo es estrictamente creciente si para cada i -ésimo índice del subarreglo, excepto el último índice, arr[i+1] > arr[i]
Ejemplos:
Entrada: arr[ ] = {7, 1, 5, 3, 6, 4}
Salida: 7
Explicación:
Todos los subarreglos crecientes posibles son {7}, {1, 5}, {3, 6} y {4}
Por lo tanto, suma = (7 – 7) + (5 – 1) + (6 – 3) + (4 – 4) = 7Entrada: array[ ] = {1, 2, 3, 4, 5, 2}
Salida: 4
Explicación:
Todos los subarreglos crecientes posibles son {1, 2, 3, 4, 5} y {2}
Por lo tanto, suma = (5 – 1) + (2 – 2) = 4
Enfoque:
siga los pasos a continuación para resolver el problema:
- Recorra el arreglo y para cada iteración, encuentre el elemento más a la derecha hasta el cual el subarreglo actual es estrictamente creciente.
- Sea i el elemento inicial del subarreglo actual y j el índice hasta el cual el subarreglo actual es estrictamente creciente. Los valores máximo y mínimo de este subarreglo serán arr[j] y arr[i] respectivamente. Entonces, agregue (arr[j] – arr[i]) a la suma .
- Continúe iterando para el siguiente subarreglo desde (j+1) th index .
- Después de completar el recorrido de la array, imprima el valor final de sum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the sum of
// differences of maximum and minimum
// of strictly increasing subarrays
#include <bits/stdc++.h>
using namespace std;
// Function to calculate and return the
// sum of differences of maximum and
// minimum of strictly increasing subarrays
int sum_of_differences(int arr[], int N)
{
// Stores the sum
int sum = 0;
int i, j, flag;
// Traverse the array
for (i = 0; i < N - 1; i++) {
if (arr[i] < arr[i + 1]) {
flag = 0;
for (j = i + 1; j < N - 1; j++) {
// If last element of the
// increasing sub-array is found
if (arr[j] >= arr[j + 1]) {
// Update sum
sum += (arr[j] - arr[i]);
i = j;
flag = 1;
break;
}
}
// If the last element of the array
// is reached
if (flag == 0 && arr[i] < arr[N - 1]) {
// Update sum
sum += (arr[N - 1] - arr[i]);
break;
}
}
}
// Return the sum
return sum;
}
// Driver Code
int main()
{
int arr[] = { 6, 1, 2, 5, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << sum_of_differences(arr, N);
return 0;
}
Java
// Java program to find the sum of
// differences of maximum and minimum
// of strictly increasing subarrays
class GFG{
// Function to calculate and return the
// sum of differences of maximum and
// minimum of strictly increasing subarrays
static int sum_of_differences(int arr[], int N)
{
// Stores the sum
int sum = 0;
int i, j, flag;
// Traverse the array
for(i = 0; i < N - 1; i++)
{
if (arr[i] < arr[i + 1])
{
flag = 0;
for(j = i + 1; j < N - 1; j++)
{
// If last element of the
// increasing sub-array is found
if (arr[j] >= arr[j + 1])
{
// Update sum
sum += (arr[j] - arr[i]);
i = j;
flag = 1;
break;
}
}
// If the last element of the array
// is reached
if (flag == 0 && arr[i] < arr[N - 1])
{
// Update sum
sum += (arr[N - 1] - arr[i]);
break;
}
}
}
// Return the sum
return sum;
}
// Driver Code
public static void main (String []args)
{
int arr[] = { 6, 1, 2, 5, 3, 4 };
int N = arr.length;
System.out.print(sum_of_differences(arr, N));
}
}
// This code is contributed by chitranayal
Python3
# Python3 program to find the sum of # differences of maximum and minimum # of strictly increasing subarrays # Function to calculate and return the # sum of differences of maximum and # minimum of strictly increasing subarrays def sum_of_differences(arr, N): # Stores the sum sum = 0 # Traverse the array i = 0 while(i < N - 1): if arr[i] < arr[i + 1]: flag = 0 for j in range(i + 1, N - 1): # If last element of the # increasing sub-array is found if arr[j] >= arr[j + 1]: # Update sum sum += (arr[j] - arr[i]) i = j flag = 1 break # If the last element of the array # is reached if flag == 0 and arr[i] < arr[N - 1]: # Update sum sum += (arr[N - 1] - arr[i]) break i += 1 # Return the sum return sum # Driver Code arr = [ 6, 1, 2, 5, 3, 4 ] N = len(arr) print(sum_of_differences(arr, N)) # This code is contributed by yatinagg
C#
// C# program to find the sum of
// differences of maximum and minimum
// of strictly increasing subarrays
using System;
class GFG{
// Function to calculate and return the
// sum of differences of maximum and
// minimum of strictly increasing subarrays
static int sum_of_differences(int []arr, int N)
{
// Stores the sum
int sum = 0;
int i, j, flag;
// Traverse the array
for(i = 0; i < N - 1; i++)
{
if (arr[i] < arr[i + 1])
{
flag = 0;
for(j = i + 1; j < N - 1; j++)
{
// If last element of the
// increasing sub-array is found
if (arr[j] >= arr[j + 1])
{
// Update sum
sum += (arr[j] - arr[i]);
i = j;
flag = 1;
break;
}
}
// If the last element of the array
// is reached
if (flag == 0 && arr[i] < arr[N - 1])
{
// Update sum
sum += (arr[N - 1] - arr[i]);
break;
}
}
}
// Return the sum
return sum;
}
// Driver Code
public static void Main (string []args)
{
int []arr = { 6, 1, 2, 5, 3, 4 };
int N = arr.Length;
Console.Write(sum_of_differences(arr, N));
}
}
// This code is contributed by rock_cool
Javascript
<script>
// Javascript program to find the sum of
// differences of maximum and minimum
// of strictly increasing subarrays
// Function to calculate and return the
// sum of differences of maximum and
// minimum of strictly increasing subarrays
function sum_of_differences(arr, N)
{
// Stores the sum
let sum = 0;
let i, j, flag;
// Traverse the array
for(i = 0; i < N - 1; i++)
{
if (arr[i] < arr[i + 1])
{
flag = 0;
for(j = i + 1; j < N - 1; j++)
{
// If last element of the
// increasing sub-array is found
if (arr[j] >= arr[j + 1])
{
// Update sum
sum += (arr[j] - arr[i]);
i = j;
flag = 1;
break;
}
}
// If the last element of the array
// is reached
if (flag == 0 && arr[i] < arr[N - 1])
{
// Update sum
sum += (arr[N - 1] - arr[i]);
break;
}
}
}
// Return the sum
return sum;
}
// Driver code
let arr = [ 6, 1, 2, 5, 3, 4 ];
let N = arr.length;
document.write(sum_of_differences(arr, N));
// This code is contributed by divyesh072019
</script>
Producción:
5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)