Рубрики

Максимизировать сумму массива после K отрицаний | Набор 2

Дан массив размером n и числом k. Мы должны изменить массив K количество раз. Здесь изменение массива означает, что в каждой операции мы можем заменить любой элемент массива arr [i] на -arr [i]. Нам нужно выполнить эту операцию таким образом, чтобы после K операций сумма массива была максимальной?

Примеры:

Input : arr[] = {-2, 0, 5, -1, 2} 
        K = 4
Output: 10
// Replace (-2) by -(-2), array becomes {2, 0, 5, -1, 2}
// Replace (-1) by -(-1), array becomes {2, 0, 5, 1, 2}
// Replace (0) by -(0), array becomes {2, 0, 5, 1, 2}
// Replace (0) by -(0), array becomes {2, 0, 5, 1, 2}

Input : arr[] = {9, 8, 8, 5} 
        K = 3
Output: 20

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Мы обсудили решение O (nk) в посте ниже.

Максимизировать сумму массива после K отрицаний | Комплект 1

Идея, использованная в посте выше, состоит в том, чтобы заменить минимальный элемент arr [i] в массиве на -arr [i] для текущей операции. Таким образом, мы можем сделать максимум массива после K операций. Если интересен случай, когда минимальный элемент становится равным 0, нам не нужно больше вносить изменения.

Реализация, использованная в вышеупомянутом решении, использует линейный поиск, чтобы найти минимальный элемент. Временная сложность рассмотренного выше решения составляет O (nk)

В этом посте реализовано оптимизированное решение, которое использует очередь приоритетов (или двоичную кучу ) для быстрого поиска минимального элемента.

Ниже приведена реализация идеи на Java. Он использует класс PriorityQueue в Java .

// Java-программа на основе PriorityQueue для максимизации массива
// сумма после k отрицаний.

import java.util.*;

  

class maximizeSum

{

    public static int maxSum(int[] a, int k)

    {

        // Создать приоритетную очередь и вставить все элементы массива

        // int

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int x : a)

            pq.add(x);

  

        // Делаем k отрицаний, удаляя минимальный элемент k раз

        while (k-- > 0)

        {

            // Получить и удалить элемент min

            int temp = pq.poll();

  

            // Изменить минимальный элемент и добавить обратно

            // в приоритетную очередь

            temp *= -1;

            pq.add(temp);

        }

  

        // Вычисляем сумму всех элементов в очереди приоритетов.

        int sum = 0;

        for (int x : pq)

            sum += x;

        return sum;

    }

  

    // Код драйвера

    public static void main (String[] args)

    {

        int[] arr = {-2, 0, 5, -1, 2};

        int k = 4;

        System.out.println(maxSum(arr, k));

    }

}

Выход:

10

Другой подход: (Эффективный подход)

// Java-программа для максимизации массива
// сумма после k отрицаний.

public class MaximizeSum {

  
// функция для максимизации массива
// сумма после k отрицаний.

static void maxSumAfterNegation(int[] a,int k){

          

        int minPos = Integer.MAX_VALUE, sum = 0, index = -1;

          

        for(int i = 0; i < a.length; i++){

              

            // Делаем k отрицаний, удаляя минимальный элемент k раз

            if(k < 0){

                break;

            }

              

            if(a[i] < 0){

                a[i]=-a[i];

                k--;

            }

              

            if(a[i] < minPos && a[i] > -1){

                minPos = a[i];

                index = i;

            }

                // Вычисляем сумму всех элементов

            sum+=a[i];

        }

          

        for(int i = k; i > 0; i--){

            a[index]=-a[index];

        }

          

        / * для (int i: a) {

            сумма + = я;

        } * /

          

        sum+=(2*a[index]);

          

        System.out.print(sum);

    }

      

    // Код драйвера

    public static void main(String[] args) {

        // TODO Автоматически генерируемый метод заглушки

  

        int[] a= {-2, 0, 5, -1, 2} ;

            MaximizeSum.maxSumAfterNegation(a, 4);

      

    }

  
}

Выход:

10

Обратите внимание, что это оптимизированное решение может быть реализовано за время O (n + kLogn), поскольку мы можем создать очередь с приоритетами (или двоичную кучу) за время O (n).

Эта статья предоставлена Прахаром . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Максимизировать сумму массива после K отрицаний | Набор 2

0.00 (0%) 0 votes