Maximice la suma de la array multiplicando el prefijo de la array con -1

Posted on by Rudeus Greyrat

Dada una array de elementos ‘arr’, la tarea es maximizar la suma de los elementos de esta array después de realizar la siguiente operación: 
puede tomar cualquier prefijo de ‘arr’ y multiplicar cada elemento del prefijo con ‘-1’. 
En la primera línea, imprime la suma maximizada que en la siguiente línea, imprime el índice hasta el cual se eligió la secuencia de prefijos.
Ejemplos: 
 

Input: arr = {1, -2, -3, 4}
Output: 10
2 1 3 2
Flip the prefix till 2nd element then the sequence is -1  2 -3  4
Flip the prefix till 1st element then the sequence is  1  2 -3  4
Flip the prefix till 3rd element then the sequence is -1 -2  3  4
Flip the prefix till 2nd element then the sequence is  1  2  3  4
And, the final maximised sum is 10

Input: arr = {1, 2, 3, 4}
Output: 10
As, all the elements are already positive.

Enfoque: la suma máxima siempre será  \small \sum \left | A_i \right | como todos los números de la array se pueden cambiar de negativo a positivo con la operación dada. 
 

  • Recorra la array de izquierda a derecha, si el elemento en el índice ‘i’ es negativo, elija ‘i’ como el índice final de la array de prefijos y multiplique cada elemento por ‘-1’.
  • Debido a la operación del paso anterior, todos los elementos de la array antes del índice ‘i’ deben ser negativos. Entonces, tome la array de prefijos que termina en el índice ‘i-1’ y aplique la misma operación nuevamente para cambiar todos los elementos a positivos.
  • Repita los pasos anteriores hasta que se haya recorrido la array completa e imprima la suma de todos los elementos junto con todos los índices finales de las arrays de prefijos elegidos al final.

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
void maxSum(int *a, int n)
{
     
    vector<int> l;
     
    // To store sum
    int s = 0;
 
    // To store ending indices
    // of the chosen prefix array vect
    for (int i = 0; i < n; i++)
    {
 
        // Adding the absolute
        // value of a[i]
        s += abs(a[i]);
        if (a[i] >= 0)
            continue;
 
        // If i == 0 then there is no index
        // to be flipped in (i-1) position
        if (i == 0)
            l.push_back(i + 1);
        else
        {
            l.push_back(i + 1);
            l.push_back(i);
        }
             
    }
 
         
    // print the maximized sum
    cout << s << endl;
 
    // print the ending indices
    // of the chosen prefix arrays
    for (int i = 0; i < l.size(); i++)
    cout << l[i] << " ";
 
}
 
// Driver Code   
int main()
{
    int n = 4;
    int a[] = {1, -2, -3, 4};
    maxSum(a, n);
}
 
// This code is contributed by
// Surendra_Gangwar

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
static void maxSum(int []a, int n)
{
    Vector<Integer> l = new Vector<Integer>();
     
    // To store sum
    int s = 0;
 
    // To store ending indices
    // of the chosen prefix array vect
    for (int i = 0; i < n; i++)
    {
 
        // Adding the absolute
        // value of a[i]
        s += Math.abs(a[i]);
        if (a[i] >= 0)
            continue;
 
        // If i == 0 then there is no index
        // to be flipped in (i-1) position
        if (i == 0)
            l.add(i + 1);
        else
        {
            l.add(i + 1);
            l.add(i);
        }
    }
 
    // print the maximised sum
    System.out.println(s);
 
    // print the ending indices
    // of the chosen prefix arrays
    for (int i = 0; i < l.size(); i++)
    System.out.print(l.get(i) + " ");
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 4;
    int a[] = {1, -2, -3, 4};
    maxSum(a, n);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python implementation of the approach
def maxSum(arr, n):
    # To store sum
    s = 0
 
    # To store ending indices
    # of the chosen prefix arrays
    l = []
    for i in range(len(a)):
 
        # Adding the absolute
        # value of a[i]
        s += abs(a[i])
        if (a[i] >= 0):
            continue
 
        # If i == 0 then there is
        # no index to be flipped
        # in (i-1) position
        if (i == 0):
            l.append(i + 1)
        else:
            l.append(i + 1)
            l.append(i)
 
    # print the
    # maximised sum
    print(s)
 
    # print the ending indices
    # of the chosen prefix arrays
    print(*l)
     
n = 4
a = [1, -2, -3, 4]
maxSum(a, n)

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
     
static void maxSum(int []a, int n)
{
    List<int> l = new List<int>();
     
    // To store sum
    int s = 0;
 
    // To store ending indices
    // of the chosen prefix array vect
    for (int i = 0; i < n; i++)
    {
 
        // Adding the absolute
        // value of a[i]
        s += Math.Abs(a[i]);
        if (a[i] >= 0)
            continue;
 
        // If i == 0 then there is no index
        // to be flipped in (i-1) position
        if (i == 0)
            l.Add(i + 1);
        else
        {
            l.Add(i + 1);
            l.Add(i);
        }
    }
 
    // print the maximised sum
    Console.WriteLine(s);
 
    // print the ending indices
    // of the chosen prefix arrays
    for (int i = 0; i < l.Count; i++)
    Console.Write(l[i] + " ");
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 4;
    int []a = {1, -2, -3, 4};
    maxSum(a, n);
}
}
 
// This code is contributed by PrinciRaj1992

PHP

<?php
// PHP implementation of the approach
function maxSum($a, $n)
{
    // To store sum
    $s = 0;
 
    // To store ending indices
    // of the chosen prefix arrays
    $l = array();
    for ($i = 0; $i < count($a); $i++)
    {
 
        // Adding the absolute
        // value of a[i]
        $s += abs($a[$i]);
        if ($a[$i] >= 0)
            continue;
 
        // If i == 0 then there is
        // no index to be flipped
        // in (i-1) position
        if ($i == 0)
            array_push($l, $i + 1);
        else
        {
            array_push($l, $i + 1);
            array_push($l, $i);
        }
    }
 
    // print the
    // maximised sum
    echo $s . "\n";
 
    // print the ending indices
    // of the chosen prefix arrays
    for($i = 0; $i < count($l); $i++)
    echo $l[$i] . " ";
}
 
// Driver Code
$n = 4;
$a = array(1, -2, -3, 4);
maxSum($a, $n);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript implementation of the above approach
 
    function maxSum(a, n)
{
    let l = [];
       
    // To store sum
    let s = 0;
   
    // To store ending indices
    // of the chosen prefix array vect
    for (let i = 0; i < n; i++)
    {
   
        // Adding the absolute
        // value of a[i]
        s += Math.abs(a[i]);
        if (a[i] >= 0)
            continue;
   
        // If i == 0 then there is no index
        // to be flipped in (i-1) position
        if (i == 0)
            l.push(i + 1);
        else
        {
            l.push(i + 1);
            l.push(i);
        }
    }
   
    // print the maximised sum
    document.write(s + "<br/>");
   
    // print the ending indices
    // of the chosen prefix arrays
    for (let i = 0; i < l.length; i++)
    document.write(l[i] + " ");
}
 
// driver code
 
    let n = 4;
    let a = [1, -2, -3, 4];
    maxSum(a, n);
   
</script>
Producción: 

10
2 1 3 2

 

Publicación traducida automáticamente

Artículo escrito por indrajit1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *