Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la máxima diferencia posible entre la suma de elementos indexados pares e impares de una subsecuencia de la array dada.
Ejemplos:
Entrada: arr[] = { 3, 2, 1, 4, 5, 2, 1, 7, 8, 9 }
Salida: 15
Explicación:
Considerando las subsecuencias { 3, 1, 5, 1, 9 } del arreglo
Sum de elementos de array indexados pares = 3 + 5 + 9 = 17
La suma de elementos de array indexados impares = es 1 + 1 = 2
Por lo tanto, la diferencia entre la suma de elementos indexados pares e impares presentes en la subsecuencia = (17 – 2) = 15, que es el máximo posible.Entrada: arr[] = {1, 2, 3, 4, 5, 6}
Salida: 6
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las subsecuencias posibles de la array dada y, para cada subsecuencia, calcular la diferencia entre la suma de los elementos indexados pares e impares de la subsecuencia. Finalmente, imprima la diferencia máxima obtenida.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es almacenar los máximos locales en índices pares de la subsecuencia y almacenar los mínimos locales en índices impares de la subsecuencia. Finalmente, imprima la diferencia entre la suma de los índices pares e impares de la subsecuencia.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos maxDiff , para almacenar la diferencia máxima entre la suma de elementos indexados pares e impares de una subsecuencia.
- Recorra la array arr[] y compruebe si arr[i] > arr[i + 1] y arr[i] < arr[i – 1] o no. Si se determina que es cierto, actualice maxDiff += arr[i] .
- De lo contrario, compruebe si arr[i] > arr[i + 1] y arr[i] < arr[i – 1] o no. Si se determina que es cierto, actualice maxDiff -= arr[i] .
- Finalmente, imprima el valor de maxDiff .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum possible difference
// between sum of even and odd indices
int maxPossibleDiff(vector<int>& arr, int N)
{
// Convert arr[] into 1-based indexing
arr.push_back(-1);
// Reverse the array
reverse(arr.begin(), arr.end());
// Convert arr[] into 1 based index
arr.push_back(-1);
// Reverse the array
reverse(arr.begin(), arr.end());
// Stores maximum difference between
// sum of even and odd indexed elements
int maxDiff = 0;
// Traverse the array
for (int i = 1; i <= N; i++) {
// If arr[i] is local maxima
if (arr[i] > arr[i - 1]
&& arr[i] > arr[i + 1]) {
// Update maxDiff
maxDiff += arr[i];
}
// If arr[i] is local minima
if (arr[i] < arr[i - 1]
&& arr[i] < arr[i + 1]) {
// Update maxDiff
maxDiff -= arr[i];
}
}
cout << maxDiff;
}
// Driver Code
int main()
{
vector<int> arr = { 3, 2, 1, 4, 5,
2, 1, 7, 8, 9 };
// Size of array
int N = arr.size();
// Function Call
maxPossibleDiff(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the maximum possible
// difference between sum of even and
// odd indices
static void maxPossibleDiff(Vector<Integer> arr, int N)
{
// Convert arr[] into 1-based indexing
arr.add(-1);
// Reverse the array
Collections.reverse(arr);
// Convert arr[] into 1 based index
arr.add(-1);
// Reverse the array
Collections.reverse(arr);
// Stores maximum difference between
// sum of even and odd indexed elements
int maxDiff = 0;
// Traverse the array
for(int i = 1; i <= N; i++)
{
// If arr.get(i) is local maxima
if (arr.get(i) > arr.get(i - 1) &&
arr.get(i) > arr.get(i + 1))
{
// Update maxDiff
maxDiff += arr.get(i);
}
// If arr.get(i) is local minima
if (arr.get(i) < arr.get(i - 1) &&
arr.get(i) < arr.get(i + 1))
{
// Update maxDiff
maxDiff -= arr.get(i);
}
}
System.out.print(maxDiff);
}
// Driver Code
public static void main(String[] args)
{
int[] array = { 3, 2, 1, 4, 5,
2, 1, 7, 8, 9 };
Vector<Integer> v = new Vector<>();
for(int i :array)
{
v.add(i);
}
// Size of array
int N = v.size();
// Function Call
maxPossibleDiff(v, N);
}
}
// This code is contributed by shikhasingrajput
Python3
#Python3 program to implement #the above approach #Function to find the maximum possible difference #between sum of even and odd indices def maxPossibleDiff(arr, N): #Convert arr[] o 1-based indexing arr.append(-1) #Reverse the array arr = arr[::-1] #Convert arr[] o 1 based index arr.append(-1) #Reverse the array arr = arr[::-1] #Stores maximum difference between #sum of even and odd indexed elements maxDiff = 0 #Traverse the array for i in range(1,N+1): #If arr[i] is local maxima if (arr[i] > arr[i - 1] and arr[i] > arr[i + 1]): #Update maxDiff maxDiff += arr[i] #If arr[i] is local minima if (arr[i] < arr[i - 1] and arr[i] < arr[i + 1]): #Update maxDiff maxDiff -= arr[i] print (maxDiff) #Driver Code if __name__ == '__main__': arr = [3, 2, 1, 4, 5, 2, 1, 7, 8, 9] #Size of array N = len(arr) #Function Call maxPossibleDiff(arr, N)
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the maximum possible
// difference between sum of even and
// odd indices
static void maxPossibleDiff(List<int> arr, int N)
{
// Convert []arr into 1-based indexing
arr.Add(-1);
// Reverse the array
arr.Reverse();
// Convert []arr into 1 based index
arr.Add(-1);
// Reverse the array
arr.Reverse();
// Stores maximum difference between
// sum of even and odd indexed elements
int maxDiff = 0;
// Traverse the array
for(int i = 1; i <= N; i++)
{
// If arr[i] is local maxima
if (arr[i] > arr[i - 1] &&
arr[i] > arr[i + 1])
{
// Update maxDiff
maxDiff += arr[i];
}
// If arr[i] is local minima
if (arr[i] < arr[i - 1] &&
arr[i] < arr[i + 1])
{
// Update maxDiff
maxDiff -= arr[i];
}
}
Console.Write(maxDiff);
}
// Driver Code
public static void Main(String[] args)
{
int[] array = { 3, 2, 1, 4, 5,
2, 1, 7, 8, 9 };
List<int> v = new List<int>();
foreach(int i in array)
{
v.Add(i);
}
// Size of array
int N = v.Count;
// Function Call
maxPossibleDiff(v, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the maximum possible difference
// between sum of even and odd indices
function maxPossibleDiff(arr, N)
{
// Convert arr[] into 1-based indexing
arr.push(-1);
// Reverse the array
arr.reverse();
// Convert arr[] into 1 based index
arr.push(-1);
// Reverse the array
arr.reverse();
// Stores maximum difference between
// sum of even and odd indexed elements
var maxDiff = 0;
// Traverse the array
for (var i = 1; i <= N; i++) {
// If arr[i] is local maxima
if (arr[i] > arr[i - 1]
&& arr[i] > arr[i + 1]) {
// Update maxDiff
maxDiff += arr[i];
}
// If arr[i] is local minima
if (arr[i] < arr[i - 1]
&& arr[i] < arr[i + 1]) {
// Update maxDiff
maxDiff -= arr[i];
}
}
document.write( maxDiff);
}
// Driver Code
var arr = [3, 2, 1, 4, 5,
2, 1, 7, 8, 9];
// Size of array
var N = arr.length;
// Function Call
maxPossibleDiff(arr, N);
</script>
15
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por swatijha0908 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA