Dada una array arr[] de tamaño N y un entero positivo K , la tarea es encontrar la suma máxima de prefijos después de K inversiones de la array dada.
Ejemplos:
Entrada: arr[] = {1, 5, 8, 9, 11, 2}, K = 1
Salida: 36
Explicación: Invierta la array una vez. Por lo tanto, la array se convierte en {2, 11, 9, 8, 5, 1}. Suma máxima de prefijos = 2 + 11 + 9 + 8 + 5 + 1 = 36.Entrada: arr[] = {5, 6, -4, 3, -2, -10}, K = 2
Salida: 11
Explicación: Invierta la array dos veces. Por lo tanto, la array se convierte en {5, 6, -4, 3, -2, -10}. Suma máxima de prefijos = 5 + 6=11.
Enfoque ingenuo: el enfoque más simple es invertir la array K veces y después de K reversiones , encontrar la suma máxima de prefijos posible al atravesar la array e imprimir la suma máxima.
Complejidad temporal: O(N * K)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en la observación de que si K es impar , entonces la array se invierte. De lo contrario, la array permanece sin cambios. Por lo tanto, si K es impar , encuentre la suma máxima de sufijos. De lo contrario, encuentre la suma máxima de prefijos. Siga los pasos a continuación para resolver el problema:
- Inicialice sum como INT_MIN para almacenar la respuesta requerida.
- Si K es impar , invierta la array arr[] .
- Inicialice currSum como 0 para almacenar la suma de elementos del prefijo.
- Recorra la array arr[] usando la variable i y realice lo siguiente:
- Agregue arr[i] a la variable currSum .
- Si el valor de currSum es mayor que sum , actualice la suma como currSum .
- Después de los pasos anteriores, imprima el valor de la suma como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum prefix
// sum after K reversals of the array
int maxSumAfterKReverse(int arr[],
int K, int N)
{
// Stores the required sum
int sum = INT_MIN;
// If K is odd, reverse the array
if (K & 1)
reverse(arr, arr + N);
// Store current prefix sum of array
int currsum = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Add arr[i] to currsum
currsum += arr[i];
// Update maximum prefix sum
// till now
sum = max(sum, currsum);
}
// Print the answer
cout << sum;
}
// Driver Code
int main()
{
int arr[] = { 1, 5, 8, 9, 11, 2 };
int K = 1;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
maxSumAfterKReverse(arr, K, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the maximum prefix
// sum after K reversals of the array
static void maxSumAfterKReverse(Integer arr[], int K, int N)
{
// Stores the required sum
int sum = Integer.MIN_VALUE;
// If K is odd, reverse the array
if (K % 2 != 0)
Collections.reverse(Arrays.asList(arr));
// Store current prefix sum of array
int currsum = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Add arr[i] to currsum
currsum += arr[i];
// Update maximum prefix sum
// till now
sum = Math.max(sum, currsum);
}
// Print the answer
System.out.print(sum);
}
// Driver Code
public static void main(String[] args)
{
Integer[] arr = { 1, 5, 8, 9, 11, 2 };
int K = 1;
int N = arr.length;
// Function Call
maxSumAfterKReverse(arr, K, N);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python3 program for the above approach import sys # Function to find the maximum prefix # sum after K reversals of the array def maxSumAfterKReverse(arr, K, N) : # Stores the required sum sum = -sys.maxsize - 1 # If K is odd, reverse the array if (K & 1) : arr.reverse() # Store current prefix sum of array currsum = 0 # Traverse the array arr[] for i in range(N): # Add arr[i] to currsum currsum += arr[i] # Update maximum prefix sum # till now sum = max(sum, currsum) # Print the answer print(sum) # Driver Code arr = [ 1, 5, 8, 9, 11, 2 ] K = 1 N = len(arr) # Function Call maxSumAfterKReverse(arr, K, N) # This code is contributed by code_hunt.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum prefix
// sum after K reversals of the array
static void maxSumAfterKReverse(int[] arr, int K, int N)
{
// Stores the required sum
int sum = Int32.MinValue;
// If K is odd, reverse the array
if (K % 2 != 0)
Array.Reverse(arr);
// Store current prefix sum of array
int currsum = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Add arr[i] to currsum
currsum += arr[i];
// Update maximum prefix sum
// till now
sum = Math.Max(sum, currsum);
}
// Print the answer
Console.Write(sum);
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 1, 5, 8, 9, 11, 2 };
int K = 1;
int N = arr.Length;
// Function Call
maxSumAfterKReverse(arr, K, N);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum prefix
// sum after K reversals of the array
function maxSumAfterKReverse(arr, K, N)
{
// Stores the required sum
let sum = Number.MIN_VALUE;
// If K is odd, reverse the array
if (K % 2 != 0)
arr.reverse();
// Store current prefix sum of array
let currsum = 0;
// Traverse the array arr[]
for (let i = 0; i < N; i++)
{
// Add arr[i] to currsum
currsum += arr[i];
// Update maximum prefix sum
// till now
sum = Math.max(sum, currsum);
}
// Print the answer
document.write(sum);
}
// Driver Code
let arr = [ 1, 5, 8, 9, 11, 2 ];
let K = 1;
let N = arr.length;
// Function Call
maxSumAfterKReverse(arr, K, N);
</script>
36
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shubhampokhriyal2018 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA