Рубрики

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

Дан массив размером 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

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

C ++

// C ++ программа для максимизации суммы массива после
// k операций.
#include<bits/stdc++.h>

using namespace std;

  
// Эта функция делает k операций над массивом
// таким образом, чтобы максимизировать сумму массива.
// index -> сохраняет индекс текущего минимума
// элемент для j-й операции

int maximumSum(int arr[], int n, int k)

{

    // Модифицировать массив K количество раз

    for (int i=1; i<=k; i++)

    {

        int min = INT_MAX;

        int index = -1;

  

        // Найти минимальный элемент в массиве для

        // текущая операция и ее изменение

        // т.е. arr [j] -> -arr [j]

        for (int j=0; j<n; j++)

        {

            if (arr[j] < min)

            {

                min = arr[j];

                index = j;

            }

        }

  

        // это условие, если мы находим 0 как

        // минимальный элемент, поэтому он будет бесполезен для

        // заменим 0 на - (0) для оставшихся операций

        if (min == 0)

            break;

  

        // Модифицировать элемент массива

        arr[index] = -arr[index];

    }

  

    // Рассчитать сумму массива

    int sum = 0;

    for (int i=0; i<n; i++)

        sum += arr[i];

    return sum;

}

  
// Драйвер программы для проверки кейса

int main()

{

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

    int k = 4;

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << maximumSum(arr, n, k);

    return 0;

}

Джава

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

  

class GFG

{

    // Эта функция делает k операций

    // на массиве таким образом, чтобы максимизировать

    // сумма массива. index -> магазины

    // индекс текущего минимума

    // элемент для j-й операции

    static int maximumSum(int arr[], int n, int k)

    {

        // Модифицировать массив K количество раз

        for (int i = 1; i <= k; i++)

        {

            int min = +2147483647;

            int index = -1;

      

            // Найти минимальный элемент в массиве для

            // текущая операция и ее изменение

            // т.е. arr [j] -> -arr [j]

            for (int j=0; j<n; j++)

            {

                if (arr[j] < min)

                {

                    min = arr[j];

                    index = j;

                }

            }

      

            // это условие, если мы находим 0 как

            // минимальный элемент, поэтому он будет бесполезен для

            // заменим 0 на - (0) для оставшихся операций

            if (min == 0)

                break;

      

            // Модифицировать элемент массива

            arr[index] = -arr[index];

        }

      

        // Рассчитать сумму массива

        int sum = 0;

        for (int i = 0; i < n; i++)

            sum += arr[i];

        return sum;

    }

      

      

    // Драйвер программы

    public static void main(String arg[])

    {

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

        int k = 4;

        int n = arr.length;

        System.out.print(maximumSum(arr, n, k));

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python3 программа для максимизации
# сумма массива после k операций.

  
# Эта функция делает k операций над массивом
# таким образом, чтобы максимизировать сумму массива.
# index -> сохраняет индекс текущего
# минимальный элемент для j-й операции

def maximumSum(arr, n, k):

  

    # Изменить массив K количество раз

    for i in range(1, k + 1):

      

        min = +2147483647

        index = -1

  

        # Найти минимальный элемент в массиве для

        # текущая операция и ее изменение

        # т.е. arr [j] -> -arr [j]

        for j in range(n):

          

            if (arr[j] < min):

              

                min = arr[j]

                index = j

  

        # это условие, если мы находим 0 как

        # минимальный элемент, поэтому он будет бесполезен для

        # заменить 0 на - (0) для оставшихся операций

        if (min == 0):

            break

  

        # Изменить элемент массива

        arr[index] = -arr[index]

      

  

    # Рассчитать сумму массива

    sum = 0

    for i in range(n):

        sum += arr[i]

    return sum

  
# Драйверная программа

arr = [-2, 0, 5, -1, 2]

k = 4

n = len(arr)

print(maximumSum(arr, n, k))

  
# Этот код предоставлен Anant Agarwal.

C #

// C # программа для максимизации массива
// сумма после k операций.

using System;

  

class GFG

{

      

    // Эта функция делает k операций

    // на массиве таким образом, чтобы максимизировать

    // сумма массива. index -> магазины

    // индекс текущего минимума

    // элемент для j-й операции

    static int maximumSum(int []arr, int n, 

                          int k)

    {

          

        // Модифицировать массив K количество раз

        for (int i = 1; i <= k; i++)

        {

            int min = +2147483647;

            int index = -1;

      

            // Найти минимальный элемент в массиве для

            // текущая операция и ее изменение

            // т.е. arr [j] -> -arr [j]

            for (int j = 0; j < n; j++)

            {

                if (arr[j] < min)

                {

                    min = arr[j];

                    index = j;

                }

            }

      

            // это условие, если мы найдем

            // 0 как минимальный элемент, так что

            // бесполезно заменить 0 на - (0)

            // для оставшихся операций

            if (min == 0)

                break;

      

            // Модифицировать элемент массива

            arr[index] = -arr[index];

        }

      

        // Рассчитать сумму массива

        int sum = 0;

        for (int i = 0; i < n; i++)

            sum += arr[i];

        return sum;

    }

      

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

    public static void Main()

    {

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

        int k = 4;

        int n = arr.Length;

        Console.Write(maximumSum(arr, n, k));

    }

}

  
// Этот код предоставлен Нитином Митталом.

PHP

<?php
// PHP программа для максимизации
// сумма массива после k операций.

  
// Эта функция делает k операций
// на массиве таким образом, чтобы максимизировать
// сумма массива. index -> магазины
// индекс текущего минимума
// элемент для j-й операции

function maximumSum($arr, $n, $k)

{

    $INT_MAX = 0;

    // Модифицировать массив K

    // количество раз

    for ($i = 1; $i <= $k; $i++)

    {

        $min = $INT_MAX;

        $index = -1;

  

        // Найти минимальный элемент в

        // массив для текущей операции

        // и модифицируем его т.е.

        // arr [j] -> -arr [j]

        for ($j = 0; $j < $n; $j++)

        {

            if ($arr[$j] < $min)

            {

                $min = $arr[$j];

                $index = $j;

            }

        }

  

        // это условие, если мы

        // найти 0 как минимальный элемент, так

        // заменить 0 будет бесполезно

        // by - (0) для оставшихся операций

        if ($min == 0)

            break;

  

        // Модифицировать элемент массива

        $arr[$index] = -$arr[$index];

    }

  

    // Рассчитать сумму массива

    $sum = 0;

    for ($i = 0; $i < $n; $i++)

        $sum += $arr[$i];

    return $sum;

}

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

$arr = array(-2, 0, 5, -1, 2);

$k = 4;

$n = sizeof($arr) / sizeof($arr[0]);

echo maximumSum($arr, $n, $k);

      
// Этот код добавлен
// нитин митталь.
?>


Выход :

10

Сложность времени: O (k * n)
Вспомогательное пространство: O (1)

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

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

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

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

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

0.00 (0%) 0 votes