Рубрики

Максимальная сумма подмассива в массиве, созданном после повторной конкатенации

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

Примеры :

Input  : arr[] = {-1, 10, 20}, k = 2
Output : 59
After concatenating array twice, we 
get {-1, 10, 20, -1, 10, 20} which has 
maximum subarray sum as 59.

Input  : arr[] = {-1, -2, -3}, k = 3
Output : -1

Простое решение — создать массив размером n * k, а затем запустить алгоритм Кадане . Временная сложность будет O (nk), а вспомогательное пространство будет O (n * k)

Лучшее решение — запустить цикл в одном и том же массиве и использовать модульную арифметику для перемещения назад, начиная с конца массива.

C ++

// C ++ программа для печати наибольшего смежного
// сумма массива при создании массива после
// конкатенация небольшого массива k раз.
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает сумму максимальной суммы созданного подмассива
// после конкатенации [0..n-1] k раз.

int maxSubArraySumRepeated(int a[], int n, int k)

{

    int max_so_far = INT_MIN, max_ending_here = 0;

  

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

    {

        // Это то, чем отличается от Кадане

        // алгоритм. Мы используем модульную арифметику для

        // найти следующий элемент.

        max_ending_here = max_ending_here + a[i%n];

  

        if (max_so_far < max_ending_here)

            max_so_far = max_ending_here;

  

        if (max_ending_here < 0)

            max_ending_here = 0;

    }

    return max_so_far;

}

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

int main()

{

    int a[] = {10, 20, -30, -1};

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

    int k = 3;

    cout << "Maximum contiguous sum is "

         << maxSubArraySumRepeated(a, n, k);

    return 0;

}

Джава

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

import java.io.*;

  

class GFG {

      
// Возвращает сумму максимальной суммы
// подмассив создан после
// объединяем [0..n-1] k раз.

static int maxSubArraySumRepeated(int a[],

                             int n, int k)

{

    int max_so_far = 0;

    int INT_MIN, max_ending_here=0;

  

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

    {

        // Это то, чем оно отличается от

        // Алгоритм Кадане. Мы используем модульные

        // арифметика для поиска следующего элемента.

        max_ending_here = max_ending_here +

                                    a[i % n];

  

        if (max_so_far < max_ending_here)

            max_so_far = max_ending_here;

  

        if (max_ending_here < 0)

            max_ending_here = 0;

    }

    return max_so_far;

}

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

public static void main (String[] args) {

      

    int a[] = {10, 20, -30, -1};

    int n = a.length;

    int k = 3;

      

    System.out.println("Maximum contiguous sum is "

                   + maxSubArraySumRepeated(a, n, k));

}

  
}

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

python3

# Python программа для печати
# крупнейший смежный
# сумма массива при массиве
# создается после
# конкатенация небольшой
# массив k раз.

  
# Возвращает сумму максимума
# сумма подмассива создана
# после объединения
# a [0..n-1] k раз.

def maxSubArraySumRepeated(a, n, k):

  

    max_so_far = -2147483648

    max_ending_here = 0

   

    for i in range(n*k):

      

        # Это где

        # отличается от Кадана

        # алгоритм. Мы используем

        # модульная арифметика для

        # найти следующий элемент.

        max_ending_here = max_ending_here + a[i%n]

   

        if (max_so_far < max_ending_here):

            max_so_far = max_ending_here

   

        if (max_ending_here < 0):

            max_ending_here = 0

      

    return max_so_far

   
# Драйверная программа
# проверить maxSubArraySum

  

a = [10, 20, -30, -1]

n = len(a)

k = 3

  

print("Maximum contiguous sum is ",

    maxSubArraySumRepeated(a, n, k))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для печати наибольшего смежного
// сумма массива при создании массива после
// конкатенация небольшого массива k раз.

using System;

  

class GFG {

      
// Возвращает сумму максимальной суммы
// подмассив создан после
// объединяем [0..n-1] k раз.

static int maxSubArraySumRepeated(int []a, 

                                  int n, 

                                  int k)

{

    int max_so_far = 0;

    int max_ending_here=0;

  

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

    {

        // Это то, чем оно отличается от

        // Алгоритм Кадане. Мы используем модульные

        // арифметика для поиска следующего элемента.

        max_ending_here = max_ending_here +

                                  a[i % n];

  

        if (max_so_far < max_ending_here)

            max_so_far = max_ending_here;

  

        if (max_ending_here < 0)

            max_ending_here = 0;

    }

    return max_so_far;

}

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

public static void Main ()

{

      

    int []a = {10, 20, -30, -1};

    int n = a.Length;

    int k = 3;

      

    Console.Write("Maximum contiguous sum is "

                  + maxSubArraySumRepeated(a, n, k));

}
}

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

PHP

<?php
// PHP программа для печати самых больших смежных
// сумма массива при создании массива после
// конкатенация небольшого массива k раз.

  
// Возвращает сумму максимума
// сумма подмассива создана
// после объединения
// a [0..n-1] k раз.

function maxSubArraySumRepeated($a, $n, $k)

{

    $INT_MIN=0; 

    $max_so_far = $INT_MIN; $max_ending_here = 0;

  

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

    {

          

        // Это то, чем оно отличается

        // из алгоритма Кадане.

        // Используем модульную арифметику

        // найти следующий элемент.

        $max_ending_here = $max_ending_here

                                  $a[$i % $n];

  

        if ($max_so_far < $max_ending_here)

            $max_so_far = $max_ending_here;

  

        if ($max_ending_here < 0)

            $max_ending_here = 0;

    }

    return $max_so_far;

}

  

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

    $a = array(10, 20, -30, -1);

    $n = sizeof($a);

    $k = 3;

    echo "Maximum contiguous sum is "

          , maxSubArraySumRepeated($a, $n, $k);

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

Выход :

Maximum contiguous sum is 30

Можем ли мы использовать повторяющееся свойство массива, чтобы получить лучшее решение?

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

Максимальная сумма подмассива в массиве, созданном после повторной конкатенации

0.00 (0%) 0 votes