Рубрики

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

Учитывая массив положительных чисел, найдите максимальную сумму подпоследовательности с ограничением, что никакие 2 числа в последовательности не должны быть смежными в массиве. Таким образом, 3 2 7 10 должно вернуть 13 (сумма 3 и 10) или 3 2 5 10 7 должно вернуть 15 (сумма 3, 5 и 7). Ответьте на вопрос наиболее эффективным способом.

Примеры :

Input : arr[] = {5, 5, 10, 100, 10, 5}
Output : 110

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

Input : arr[] = {1, 20, 3}
Output : 20

Алгоритм:
Цикл для всех элементов в arr [] и поддерживает две суммы incl и excl, где incl = Макс. Сумма, включая предыдущий элемент, и excl = Макс. Сумма, исключая предыдущий элемент.

Максимальная сумма, исключая текущий элемент, будет равна max (вкл., Исключая), а максимальная сумма, включая текущий элемент, будет составлять + текущий элемент (обратите внимание, что рассматривается только исключение, поскольку элементы не могут быть смежными).

В конце цикла верните макс. Вкл. И вкл.

Пример:

  arr[] = {5,  5, 10, 40, 50, 35}

  incl = 5 
  excl = 0

  For i = 1 (current element is 5)
  incl =  (excl + arr[i])  = 5
  excl =  max(5, 0) = 5

  For i = 2 (current element is 10)
  incl =  (excl + arr[i]) = 15
  excl =  max(5, 5) = 5

  For i = 3 (current element is 40)
  incl = (excl + arr[i]) = 45
  excl = max(5, 15) = 15

  For i = 4 (current element is 50)
  incl = (excl + arr[i]) = 65
  excl =  max(45, 15) = 45

  For i = 5 (current element is 35)
  incl =  (excl + arr[i]) = 80
  excl =  max(65, 45) = 65

And 35 is the last element. So, answer is max(incl, excl) =  80

Спасибо Debanjan за предоставление кода.

Реализация:

C / C ++

#include<stdio.h>

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

 являются смежными *

int FindMaxSum(int arr[], int n)

{

  int incl = arr[0];

  int excl = 0;

  int excl_new;

  int i;

  

  for (i = 1; i < n; i++)

  {

     / * ток максимальный, исключая я * /

     excl_new = (incl > excl)? incl: excl;

  

     / * максимальный ток, включая I * /

     incl = excl + arr[i];

     excl = excl_new;

  }

  

   / * вернуть максимум вкл. и исключ. * /

   return ((incl > excl)? incl : excl);

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  int arr[] = {5, 5, 10, 100, 10, 5};

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

  printf("%d n", FindMaxSum(arr, n));

  return 0;

}

Джава

class MaximumSum

{

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

      являются смежными *

    int FindMaxSum(int arr[], int n)

    {

        int incl = arr[0];

        int excl = 0;

        int excl_new;

        int i;

  

        for (i = 1; i < n; i++)

        {

            / * ток максимальный, исключая я * /

            excl_new = (incl > excl) ? incl : excl;

  

            / * максимальный ток, включая I * /

            incl = excl + arr[i];

            excl = excl_new;

        }

  

        / * вернуть максимум вкл. и исключ. * /

        return ((incl > excl) ? incl : excl);

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        MaximumSum sum = new MaximumSum();

        int arr[] = new int[]{5, 5, 10, 100, 10, 5};

        System.out.println(sum.FindMaxSum(arr, arr.length));

    }

}

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

питон

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

def find_max_sum(arr):

    incl = 0

    excl = 0

     

    for i in arr:

          

        # Максимальный ток, исключая я (без троичного в

        # Python)

        new_excl = excl if excl>incl else incl

         

        # Максимальный ток, включая меня

        incl = excl + i

        excl = new_excl

      

    # вернуть максимум вкл и исключ

    return (excl if excl>incl else incl)

  
# Программа драйвера для проверки вышеуказанной функции

arr = [5, 5, 10, 100, 10, 5]

print find_max_sum(arr)

  
# Этот код предоставлен Kalai Selvan

C #

/ * Программа для возврата максимальной суммы, такой что нет
два элемента смежны * /

using System;

  

class GFG {

      

    / * Функция для возврата максимальной суммы, такой

    что нет двух соседних элементов * /

    static int FindMaxSum(int []arr, int n)

    {

        int incl = arr[0];

        int excl = 0;

        int excl_new;

        int i;

  

        for (i = 1; i < n; i++)

        {

            / * ток максимальный, исключая я * /

            excl_new = (incl > excl) ? 

                            incl : excl;

  

            / * максимальный ток, включая I * /

            incl = excl + arr[i];

            excl = excl_new;

        }

  

        / * вернуть максимум вкл. и исключ. * /

        return ((incl > excl) ? 

                            incl : excl);

    }

  

    // Программа драйвера для тестирования выше

    // функции

    public static void Main()

    {

        int []arr = new int[]{5, 5, 10,

                              100, 10, 5};

                                

        Console.Write(

             FindMaxSum(arr, arr.Length));

    }

}

  
// Этот код был добавлен
// нитин митталь

PHP

<?php
// PHP-код для поиска максимальной суммы
// такой, что нет двух элементов
// смежны

  
/ * Функция для возврата максимальной суммы

   такой, что нет двух элементов

   являются смежными *

function FindMaxSum($arr, $n)

{

    $incl = $arr[0];

    $excl = 0;

    $excl_new;

    $i;

  

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

{

      

    // текущий максимум за исключением i

    $excl_new = ($incl > $excl)? $incl: $excl;

  

    // текущий максимум включая меня

    $incl = $excl + $arr[$i];

    $excl = $excl_new;

}

  
// вернуть максимум из incl и excl

return (($incl > $excl)? $incl : $excl);

}

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

$arr = array(5, 5, 10, 100, 10, 5);

$n = sizeof($arr);

echo FindMaxSum($arr, $n);

      
// Этот код предоставлен Ajit
?>


Выход:

110

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

См. Найти максимально возможную украденную стоимость из домов для получения более подробных объяснений.

Теперь попробуйте ту же проблему для массива с отрицательными числами.

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в вышеуказанной программе / алгоритме или другие способы решения той же проблемы.

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

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

0.00 (0%) 0 votes