Dada una array arr[] , la tarea es maximizar la suma de los elementos indexados pares invirtiendo una subarreglo e imprimir la suma máxima obtenida.
Ejemplos:
Entrada: arr[] = {1, 2, 1, 2, 1}
Salida: 5
Explicación:
Suma de elementos indexados pares iniciales = a[0] + a[2] + a[4] = 1 + 1 + 1 = 3
Invertir el subarreglo {1, 2, 1, 2} modifica el arreglo a {2, 1, 2, 1, 1}.
Por lo tanto, la suma maximizada = 2 + 2 + 1 = 5Entrada: arr[] = {7, 8, 4, 5, 7, 6, 8, 9, 7, 3}
Salida: 37
Enfoque ingenuo:
el enfoque más simple para resolver el problema es generar todas las permutaciones posibles mediante la inversión de elementos uno por uno y calcular la suma en índices pares para cada permutación. Imprime la suma máxima posible entre todas las permutaciones.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente:
el enfoque anterior se puede optimizar aún más para la complejidad computacional O(N) mediante el uso de la programación dinámica para verificar la diferencia máxima mediante la rotación de arrays.
Siga los pasos a continuación para resolver el problema:
- Compare los elementos en el índice impar con el índice par y también realice un seguimiento de ellos.
- Inicialice dos arrays leftDP[] y rightDP[] .
- Para cada índice impar, leftDP[] almacena la diferencia del elemento en el índice actual con el elemento a su izquierda y rightDP[] almacena la de la derecha.
- Si la diferencia calculada para el índice anterior es positiva, súmela a la diferencia actual:
if(dp[i – 1] > 0)
dp[i] = dp[i-1] + curr_diff
- De lo contrario, almacene la diferencia actual:
dp[i] = diferencia_actual;
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 return maximized sum
// at even indices
int maximizeSum(int arr[], int n)
{
int sum = 0;
for(int i = 0; i < n; i = i + 2)
sum += arr[i];
// Stores difference with
// element on the left
int leftDP[n / 2];
// Stores difference with
// element on the right
int rightDP[n / 2];
int c = 0;
for(int i = 1; i < n; i = i + 2)
{
// Compute and store
// left difference
int leftDiff = arr[i] - arr[i - 1];
// For first index
if (c - 1 < 0)
leftDP = leftDiff;
else
{
// If previous difference
// is positive
if (leftDP > 0)
leftDP = leftDiff + leftDP;
// Otherwise
else
leftDP[i] = leftDiff;
}
int rightDiff;
// For the last index
if (i + 1 >= n)
rightDiff = 0;
// Otherwise
else
rightDiff = arr[i] - arr[i + 1];
// For first index
if (c - 1 < 0)
rightDP = rightDiff;
else
{
// If the previous difference
// is positive
if (rightDP > 0)
rightDP = rightDiff +
rightDP;
else
rightDP = rightDiff;
}
c++;
}
int maxi = 0;
for(int i = 0; i < n / 2; i++)
{
maxi = max(maxi, max(leftDP[i],
rightDP[i]));
}
return maxi + sum;
}
// Driver Code
int main()
{
int arr[] = { 7, 8, 4, 5, 7,
6, 8, 9, 7, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int ans = maximizeSum(arr, n);
cout << (ans);
}
// This code is contributed by chitranayal
Java
// Java Program to implement
// the above approach
import java.io.*;
class GFG {
// Function to return maximized sum
// at even indices
public static int maximizeSum(int[] arr)
{
int n = arr.length;
int sum = 0;
for (int i = 0; i < n; i = i + 2)
sum += arr[i];
// Stores difference with
// element on the left
int leftDP[] = new int[n / 2];
// Stores difference with
// element on the right
int rightDP[] = new int[n / 2];
int c = 0;
for (int i = 1; i < n; i = i + 2) {
// Compute and store
// left difference
int leftDiff = arr[i]
- arr[i - 1];
// For first index
if (c - 1 < 0)
leftDP = leftDiff;
else {
// If previous difference
// is positive
if (leftDP > 0)
leftDP = leftDiff
+ leftDP;
// Otherwise
else
leftDP[i] = leftDiff;
}
int rightDiff;
// For the last index
if (i + 1 >= arr.length)
rightDiff = 0;
// Otherwise
else
rightDiff = arr[i]
- arr[i + 1];
// For first index
if (c - 1 < 0)
rightDP = rightDiff;
else {
// If the previous difference
// is positive
if (rightDP > 0)
rightDP = rightDiff
+ rightDP;
else
rightDP = rightDiff;
}
c++;
}
int max = 0;
for (int i = 0; i < n / 2; i++) {
max = Math.max(max,
Math.max(
leftDP[i],
rightDP[i]));
}
return max + sum;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 7, 8, 4, 5, 7, 6,
8, 9, 7, 3 };
int ans = maximizeSum(arr);
System.out.println(ans);
}
}
Python3
# Python3 program to implement # the above approach # Function to return maximized sum # at even indices def maximizeSum(arr): n = len(arr) sum = 0 for i in range(0, n, 2): sum += arr[i] # Stores difference with # element on the left leftDP = [0] * (n) # Stores difference with # element on the right rightDP = [0] * (n) c = 0 for i in range(1, n, 2): # Compute and store # left difference leftDiff = arr[i] - arr[i - 1] # For first index if (c - 1 < 0): leftDP[i] = leftDiff else: # If previous difference # is positive if (leftDP[i] > 0): leftDP[i] = (leftDiff + leftDP[i - 1]) # Otherwise else: leftDP[i] = leftDiff rightDiff = 0 # For the last index if (i + 1 >= len(arr)): rightDiff = 0 # Otherwise else: rightDiff = arr[i] - arr[i + 1] # For first index if (c - 1 < 0): rightDP[i] = rightDiff else: # If the previous difference # is positive if (rightDP[i] > 0): rightDP[i] = (rightDiff + rightDP[i - 1]) else: rightDP[i] = rightDiff c += 1 maxm = 0 for i in range(n // 2): maxm = max(maxm, max(leftDP[i], rightDP[i])) return maxm + sum # Driver Code if __name__ == '__main__': arr = [ 7, 8, 4, 5, 7, 6, 8, 9, 7, 3 ] ans = maximizeSum(arr) print(ans) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to return maximized sum
// at even indices
public static int maximizeSum(int[] arr)
{
int n = arr.Length;
int sum = 0;
for(int i = 0; i < n; i = i + 2)
sum += arr[i];
// Stores difference with
// element on the left
int []leftDP = new int[n / 2];
// Stores difference with
// element on the right
int []rightDP = new int[n / 2];
int c = 0;
for(int i = 1; i < n; i = i + 2)
{
// Compute and store
// left difference
int leftDiff = arr[i] - arr[i - 1];
// For first index
if (c - 1 < 0)
leftDP = leftDiff;
else
{
// If previous difference
// is positive
if (leftDP > 0)
leftDP = leftDiff +
leftDP;
// Otherwise
else
leftDP = leftDiff;
}
int rightDiff;
// For the last index
if (i + 1 >= arr.Length)
rightDiff = 0;
// Otherwise
else
rightDiff = arr[i] - arr[i + 1];
// For first index
if (c - 1 < 0)
rightDP = rightDiff;
else
{
// If the previous difference
// is positive
if (rightDP > 0)
rightDP = rightDiff +
rightDP;
else
rightDP = rightDiff;
}
c++;
}
int max = 0;
for(int i = 0; i < n / 2; i++)
{
max = Math.Max(max,
Math.Max(leftDP[i],
rightDP[i]));
}
return max + sum;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 7, 8, 4, 5, 7, 6,
8, 9, 7, 3 };
int ans = maximizeSum(arr);
Console.WriteLine(ans);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to return maximized sum
// at even indices
function maximizeSum(arr)
{
let n = arr.length;
let sum = 0;
for (let i = 0; i < n; i = i + 2)
sum += arr[i];
// Stores difference with
// element on the left
let leftDP = new Array(Math.floor(n / 2));
// Stores difference with
// element on the right
let rightDP = new Array(Math.floor(n / 2));
for(let i=0;i<n/2;i++)
{
leftDP[i]=0;
rightDP[i]=0;
}
let c = 0;
for (let i = 1; i < n; i = i + 2) {
// Compute and store
// left difference
let leftDiff = arr[i]
- arr[i - 1];
// For first index
if (c - 1 < 0)
leftDP[i] = leftDiff;
else {
// If previous difference
// is positive
if (leftDP[i] > 0)
leftDP[i] = leftDiff
+ leftDP[i-1];
// Otherwise
else
leftDP[i] = leftDiff;
}
let rightDiff;
// For the last index
if (i + 1 >= arr.length)
rightDiff = 0;
// Otherwise
else
rightDiff = arr[i]
- arr[i + 1];
// For first index
if (c - 1 < 0)
rightDP[i] = rightDiff;
else {
// If the previous difference
// is positive
if (rightDP[i] > 0)
rightDP[i] = rightDiff
+ rightDP[i-1];
else
rightDP[i] = rightDiff;
}
c++;
}
let max = 0;
for (let i = 0; i < n / 2; i++) {
max = Math.max(max,
Math.max(
leftDP[i],
rightDP[i]));
}
return max + sum;
}
// Driver Code
let arr=[7, 8, 4, 5, 7, 6,
8, 9, 7, 3];
let ans = maximizeSum(arr);
document.write(ans);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
37
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por yogeshsherawat77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA