Dada una array arr[] que consta de N pares, cada uno de los cuales consta de una string y un valor entero correspondiente a esa string . La tarea es encontrar el subarreglo de suma absoluta máxima e imprimir las strings correspondientes a los elementos del subarreglo.
Ejemplos:
Entrada: arr[] = {(“geeks”, 4), (“for”, -3), (“geeks”, 2), (“tutorial”, 3), (“programa”, -4)}
Salida : tutorial de geeks para geeks
Explicación: El subarreglo de suma absoluta máxima es {arr[0], .. arr[3]}, con suma 6. Por lo tanto, las strings correspondientes entre estos valores son «geeks», «for», «geeks» y “tutorial”.Entrada: arr[]= {(“práctica”, -7), (“hace”, 2 ), (“hombres perfectos”, 5)}
Salida: práctica
Explicación: El subarreglo de suma absoluta máxima es {arr[0]} , teniendo suma 7. Por lo tanto, la string correspondiente es «práctica».
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles para encontrar el subarreglo de suma máxima. Luego, imprima la string correspondiente a ese subarreglo.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea óptima es usar el algoritmo de Kadane con alguna modificación para que pueda manejar valores negativos y elegir el máximo entre el valor mínimo absoluto y el valor máximo absoluto.
Siga los pasos a continuación para resolver el problema:
- Initializevariables, res = 0 , para almacenar la respuesta final y start = 0 , end = 0 para almacenar los índices inicial y final del subarreglo requerido.
- Inicialice dos variables más, digamos posPrefix y negPrefix , para almacenar el valor de prefijo positivo anterior y el valor de prefijo negativo.
- Atraviese la array arr[] y realice lo siguiente
- Si el elemento actual es negativo, y si el valor de arr[i] + negPrefix > res , actualice el valor de res, índice de inicio y fin .
- Si el elemento actual es positivo, y si el valor de arr[i] + posPrefix > res , actualice el valor de res, índice de inicio y final .
- Verifique si agregar el elemento actual a negPrefix lo hace mayor o igual a 0 , luego actualice start = i + 1 y establezca negPrefix = 0 de lo contrario, agregue el valor actual a negPrefix .
- Verifique si agregar el elemento actual a posPrefix lo hace menor o igual a 0 , luego actualice start = i + 1 y establezca posPrefix = 0 de lo contrario, agregue el valor actual a posPrefix .
- Finalmente, recorra la array en el rango [inicio, fin] e imprima las strings correspondientes.
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 print strings corresponding
// to the elements present in the subarray
// with maximum absolute sum
void maximumAbsSum(pair<string, int>* arr,
int N)
{
int start = 0, end = 0, res = 0,
negIndex = 0, posIndex = 0,
negPrefix = 0, posPrefix = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
if (arr[i].second < 0) {
// If adding current element
// to negative
// prefix makes it > res
// then update the values
if (res < abs(arr[i].second
+ negPrefix)) {
res = abs(arr[i].second
+ negPrefix);
start = negIndex;
end = i;
}
}
else {
// If adding current element to
// positive prefix exceeds res
if (res < abs(arr[i].second
+ posPrefix)) {
res = abs(arr[i].second
+ posPrefix);
start = posIndex;
end = i;
}
}
// Since negPrefix > 0, there is
// no benefit in adding it to a
// negative value
if (negPrefix + arr[i].second > 0) {
negPrefix = 0;
negIndex = i + 1;
}
// Since negative + negative
// generates a larger negative value
else {
negPrefix += arr[i].second;
}
// Since positive + positive
// generates a larger positive number
if (posPrefix + arr[i].second >= 0) {
posPrefix += arr[i].second;
}
// Since pos_prefix < 0, there is
// no benefit in adding it to
// a positive value
else {
posPrefix = 0;
posIndex = i + 1;
}
}
// Print the corresponding strings
for (int i = start; i <= end; i++) {
cout << arr[i].first << " ";
}
}
// Driver Code
int main()
{
// Given array
pair<string, int> arr[] = { { "geeks", 4 },
{ "for", -3 },
{ "geeks", 2 },
{ "tutorial", 3 },
{ "program", -4 } };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Function call to print
// string corresponding to
// maximum absolute subarray sum
maximumAbsSum(arr, N);
}
Java
// Java program for the above approach
class GFG
{
static class pair<E,R>
{
E first;
R second;
public pair(E first, R second)
{
this.first = first;
this.second = second;
}
}
// Function to print Strings corresponding
// to the elements present in the subarray
// with maximum absolute sum
static void maximumAbsSum(pair<String,Integer> []arr,
int N)
{
int start = 0, end = 0, res = 0,
negIndex = 0, posIndex = 0,
negPrefix = 0, posPrefix = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
if (arr[i].second < 0)
{
// If adding current element
// to negative
// prefix makes it > res
// then update the values
if (res < Math.abs(arr[i].second
+ negPrefix)) {
res = Math.abs(arr[i].second
+ negPrefix);
start = negIndex;
end = i;
}
}
else
{
// If adding current element to
// positive prefix exceeds res
if (res < Math.abs(arr[i].second
+ posPrefix)) {
res = Math.abs(arr[i].second
+ posPrefix);
start = posIndex;
end = i;
}
}
// Since negPrefix > 0, there is
// no benefit in adding it to a
// negative value
if (negPrefix + arr[i].second > 0) {
negPrefix = 0;
negIndex = i + 1;
}
// Since negative + negative
// generates a larger negative value
else {
negPrefix += arr[i].second;
}
// Since positive + positive
// generates a larger positive number
if (posPrefix + arr[i].second >= 0) {
posPrefix += arr[i].second;
}
// Since pos_prefix < 0, there is
// no benefit in adding it to
// a positive value
else {
posPrefix = 0;
posIndex = i + 1;
}
}
// Print the corresponding Strings
for (int i = start; i <= end; i++) {
System.out.print(arr[i].first+ " ");
}
}
// Driver Code
@SuppressWarnings("unchecked")
public static void main(String[] args)
{
// Given array
@SuppressWarnings("rawtypes")
pair arr[] = { new pair( "geeks", 4 ),
new pair( "for", -3 ),
new pair( "geeks", 2 ),
new pair( "tutorial", 3 ),
new pair( "program", -4 ) };
// Size of the array
int N = arr.length;
// Function call to print
// String corresponding to
// maximum absolute subarray sum
maximumAbsSum(arr, N);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to print strings corresponding # to the elements present in the subarray # with maximum absolute sum def maximumAbsSum(arr, N): start, end, res = 0, 0, 0 negIndex, posIndex = 0, 0 negPrefix, posPrefix = 0, 0 # Traverse the array for i in range(N): if (arr[i][1] < 0): # If adding current element # to negative # prefix makes it > res # then update the values if (res < abs(arr[i][1] + negPrefix)): res = abs(arr[i][1] + negPrefix) start = negIndex end = i else: # If adding current element to # positive prefix exceeds res if (res < abs(arr[i][1] + posPrefix)): res = abs(arr[i][1] + posPrefix) start = posIndex end = i # Since negPrefix > 0, there is # no benefit in adding it to a # negative value if (negPrefix + arr[i][1] > 0): negPrefix = 0 negIndex = i + 1 # Since negative + negative # generates a larger negative value else: negPrefix += arr[i][1] # Since positive + positive # generates a larger positive number if (posPrefix + arr[i][1] >= 0): posPrefix += arr[i][1] # Since pos_prefix < 0, there is # no benefit in adding it to # a positive value else: posPrefix = 0 posIndex = i + 1 # Print the corresponding strings for i in range(start, end + 1): print(arr[i][0], end = " ") # Driver Code if __name__ == '__main__': # Given array arr = [ [ "geeks", 4 ], [ "for", -3 ], [ "geeks", 2 ], [ "tutorial", 3 ], [ "program", -4 ] ] # Size of the array N = len(arr) # Function call to print # string corresponding to # maximum absolute subarray sum maximumAbsSum(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
public class pair
{
public string first;
public int second;
public pair(string first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to print Strings corresponding
// to the elements present in the subarray
// with maximum absolute sum
static void maximumAbsSum(pair []arr,
int N)
{
int start = 0, end = 0, res = 0,
negIndex = 0, posIndex = 0,
negPrefix = 0, posPrefix = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
if (arr[i].second < 0)
{
// If adding current element
// to negative
// prefix makes it > res
// then update the values
if (res < Math.Abs(arr[i].second
+ negPrefix)) {
res = Math.Abs(arr[i].second
+ negPrefix);
start = negIndex;
end = i;
}
}
else
{
// If adding current element to
// positive prefix exceeds res
if (res < Math.Abs(arr[i].second
+ posPrefix)) {
res = Math.Abs(arr[i].second
+ posPrefix);
start = posIndex;
end = i;
}
}
// Since negPrefix > 0, there is
// no benefit in adding it to a
// negative value
if (negPrefix + arr[i].second > 0) {
negPrefix = 0;
negIndex = i + 1;
}
// Since negative + negative
// generates a larger negative value
else {
negPrefix += arr[i].second;
}
// Since positive + positive
// generates a larger positive number
if (posPrefix + arr[i].second >= 0) {
posPrefix += arr[i].second;
}
// Since pos_prefix < 0, there is
// no benefit in adding it to
// a positive value
else {
posPrefix = 0;
posIndex = i + 1;
}
}
// Print the corresponding Strings
for (int i = start; i <= end; i++) {
Console.Write(arr[i].first+ " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array
pair []arr = { new pair( "geeks", 4 ),
new pair( "for", -3 ),
new pair( "geeks", 2 ),
new pair( "tutorial", 3 ),
new pair( "program", -4 ) };
// Size of the array
int N = arr.Length;
// Function call to print
// String corresponding to
// maximum absolute subarray sum
maximumAbsSum(arr, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
class pair
{
constructor(first,second)
{
this.first=first;
this.second=second;
}
}
// Function to print Strings corresponding
// to the elements present in the subarray
// with maximum absolute sum
function maximumAbsSum(arr,N)
{
let start = 0, end = 0, res = 0,
negIndex = 0, posIndex = 0,
negPrefix = 0, posPrefix = 0;
// Traverse the array
for (let i = 0; i < N; i++)
{
if (arr[i].second < 0)
{
// If adding current element
// to negative
// prefix makes it > res
// then update the values
if (res < Math.abs(arr[i].second
+ negPrefix)) {
res = Math.abs(arr[i].second
+ negPrefix);
start = negIndex;
end = i;
}
}
else
{
// If adding current element to
// positive prefix exceeds res
if (res < Math.abs(arr[i].second
+ posPrefix)) {
res = Math.abs(arr[i].second
+ posPrefix);
start = posIndex;
end = i;
}
}
// Since negPrefix > 0, there is
// no benefit in adding it to a
// negative value
if (negPrefix + arr[i].second > 0) {
negPrefix = 0;
negIndex = i + 1;
}
// Since negative + negative
// generates a larger negative value
else {
negPrefix += arr[i].second;
}
// Since positive + positive
// generates a larger positive number
if (posPrefix + arr[i].second >= 0) {
posPrefix += arr[i].second;
}
// Since pos_prefix < 0, there is
// no benefit in adding it to
// a positive value
else {
posPrefix = 0;
posIndex = i + 1;
}
}
// Print the corresponding Strings
for (let i = start; i <= end; i++) {
document.write(arr[i].first+ " ");
}
}
// Driver Code
// Given array
let arr=[new pair( "geeks", 4 ),
new pair( "for", -3 ),
new pair( "geeks", 2 ),
new pair( "tutorial", 3 ),
new pair( "program", -4 )];
// Size of the array
let N = arr.length;
// Function call to print
// String corresponding to
// maximum absolute subarray sum
maximumAbsSum(arr, N);
// This code is contributed by unknown2108
</script>
Producción:
geeks for geeks tutorial
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA