Рубрики

Максимальная сумма после K последовательных удалений

Учитывая массив arr [] размера N и целое число K , задача состоит в том, чтобы удалить K непрерывных элементов из массива так, чтобы сумма оставшегося элемента была максимальной. Здесь нам нужно распечатать остальные элементы массива.

Примеры:

Input: arr[] = {-1, 1, 2, -3, 2, 2}, K = 3
Output: -1 2 2
Delete 1, 2, -3 and the sum of the remaining
elements will be 3 which is maximum possible.

Input: arr[] = {1, 2, -3, 4, 5}, K = 1
Output: 1 2 4 5

Подход: Рассчитайте сумму k-последовательных элементов и удалите элементы с минимальной суммой. Распечатайте остальные элементы массива.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для печати массива после удаления
// k последовательных элементов, таких что сумма
// из оставшихся элементов максимизируется

void maxSumArr(int arr[], int n, int k)

{

    int cur = 0, index = 0;

  

    // Находим сумму первых k элементов

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

        cur += arr[i];

  

    // Для хранения минимальной суммы k

    // последовательные элементы массива

    int min = cur;

    for (int i = 0; i < n - k; i++) {

  

        // Расчет суммы следующих k элементов

        cur = cur - arr[i] + arr[i + k];

  

        // Обновляем минимальную сумму на данный момент и

        // индекс первого элемента

        if (cur < min) {

            cur = min;

            index = i + 1;

        }

    }

  

    // Печать результата

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

        cout << arr[i] << " ";

    for (int i = index + k; i < n; i++)

        cout << arr[i] << " ";

}

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

int main()

{

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

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

    int k = 3;

  

    maxSumArr(arr, n, k);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG {

  

    // Функция для печати массива после удаления

    // k последовательных элементов, таких что сумма

    // из оставшихся элементов максимизируется

    static void maxSumArr(int arr[], int n, int k)

    {

        int cur = 0, index = 0;

  

        // Находим сумму первых k элементов

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

            cur += arr[i];

  

        // Для хранения минимальной суммы k

        // последовательные элементы массива

        int min = cur;

        for (int i = 0; i < n - k; i++) {

  

            // Расчет суммы следующих k элементов

            cur = cur - arr[i] + arr[i + k];

  

            // Обновляем минимальную сумму на данный момент и

            // индекс первого элемента

            if (cur < min) {

                cur = min;

                index = i + 1;

            }

        }

  

        // Печать результата

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

            System.out.print(arr[i] + " ");

        for (int i = index + k; i < n; i++)

            System.out.print(arr[i] + " ");

    }

  

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

    public static void main(String[] args)

    {

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

        int n = arr.length;

        int k = 3;

  

        maxSumArr(arr, n, k);

    }

}

питон

# Pyhton3 реализация подхода

  
# Функция для печати массива после удаления
# k последовательных элементов, таких что сумма
Количество оставшихся элементов максимально

def maxSumArr(arr,  n, k):

    cur = 0

    index = 0

  

    # Найти сумму первых k элементов

    for i in range(k):

        cur += arr[i]

  

    # Для хранения минимальной суммы к

    # последовательных элементов массива

    min = cur;

    for i in range(n-k):

  

        # Расчет суммы следующих k элементов

        cur = cur-arr[i]+arr[i + k]

          

        # Обновите минимальную сумму на данный момент и

        # индекс первого элемента

        if(cur<min):

            cur = min

            index = i + 1

  

    # Результат печати

    for i in range(index):

        print(arr[i], end =" ")

    i = index + k

    while i<n:

        print(arr[i], end =" ")

        i += 1

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

arr = [-1, 1, 2, -3, 2, 2]

n = len(arr)

k = 3

  
maxSumArr(arr, n, k)

C #

// C # реализация вышеуказанного подхода

using System;

  

class GFG

{

      

    // Функция для печати массива после удаления

    // k последовательных элементов, таких что сумма

    // из оставшихся элементов максимизируется

    static void maxSumArr(int []arr, int n, int k)

    {

        int cur = 0, index = 0;

  

        // Находим сумму первых k элементов

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

            cur = cur + arr[i];

  

        // Для хранения минимальной суммы k

        // последовательные элементы массива

        int min = cur;

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

        {

  

            // Расчет суммы следующих k элементов

            cur = (cur - arr[i]) + (arr[i + k]);

  

            // Обновляем минимальную сумму на данный момент и

            // индекс первого элемента

            if (cur < min) 

            {

                cur = min;

                index = i + 1;

            }

        }

  

        // Печать результата

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

            Console.Write(arr[i] + " ");

        for (int i = index + k; i < n; i++)

            Console.Write(arr[i] + " ");

    }

  

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

    static public void Main ()

    {

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

        int n = arr.Length;

        int k = 3;

  

        maxSumArr(arr, n, k);

    }

}

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

Выход:

-1 2 2

Сложность времени: O (n)

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

Максимальная сумма после K последовательных удалений

0.00 (0%) 0 votes