Рубрики

Найти максимально возможную сумму, равную сумме трех стеков

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

Примеры:

Input : stack1[] = { 3, 10}
  stack2[] = { 4, 5 }
  stack3[] = { 2, 1 }
Output : 0
Sum can only be equal after removing all elements 
from all stacks.

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

Алгоритм решения этой проблемы:

  1. Найти сумму всех элементов в отдельных стеках.
  2. Если сумма всех трех стеков одинакова, то это максимальная сумма.
  3. Еще удалите верхний элемент стека, имеющий максимальную сумму среди трех стеков. Повторите шаг 1 и шаг 2.

Подход работает, потому что элементы являются положительными. Чтобы сделать сумму равной, мы должны удалить некоторый элемент из стека, имеющий больше суммы, и мы можем удалить только сверху.

Ниже приведена реализация этого подхода:

C / C ++

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

using namespace std;

  
// Возвращает максимально возможную равную сумму трех стеков
// с удалением верхних элементов

int maxSum(int stack1[], int stack2[], int stack3[], 

                             int n1, int n2, int n3)

{

  int sum1 = 0, sum2 = 0, sum3 = 0;

   

  // Находим начальную сумму stack1.

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

      sum1 += stack1[i];

  

  // Находим начальную сумму stack2.

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

      sum2 += stack2[i];

  

  // Находим начальную сумму stack3.

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

      sum3 += stack3[i];

  

  // Как указано в вопросе, первый элемент является верхним

  // стека

  int top1 =0, top2 = 0, top3 = 0;

  int ans = 0;

  while (1)

  {

      // Если какой-либо стек пуст

      if (top1 == n1 || top2 == n2 || top3 == n3)

         return 0;

  

      // Если сумма всех трех стеков равна.

      if (sum1 == sum2 && sum2 == sum3)

         return sum1;

      

      // Находим стек с максимальной суммой и

      // удаляем его верхний элемент.

      if (sum1 >= sum2 && sum1 >= sum3)

         sum1 -= stack1[top1++];

      else if (sum2 >= sum3 && sum2 >= sum3)

         sum2 -= stack2[top2++];

      else if (sum3 >= sum2 && sum3 >= sum1)

         sum3 -= stack3[top3++];

   }

}

  
// Управляемая программа

int main()

{

  int stack1[] = { 3, 2, 1, 1, 1 };

  int stack2[] = { 4, 3, 2 };

  int stack3[] = { 1, 1, 4, 1 };

  

  int n1 = sizeof(stack1)/sizeof(stack1[0]);

  int n2 = sizeof(stack2)/sizeof(stack2[0]);

  int n3 = sizeof(stack3)/sizeof(stack3[0]);

  

  cout << maxSum(stack1, stack2, stack3, n1, n2, n3) << endl;

  return 0;

Джава

// JAVA-код для поиска максимально возможной суммы
// равная сумма трех стеков

class GFG {

       

    // Возвращает максимально возможную равную сумму трех

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

    public static int maxSum(int stack1[], int stack2[],

                            int stack3[], int n1, int n2,

                                               int n3)

    {

      int sum1 = 0, sum2 = 0, sum3 = 0;

        

      // Находим начальную сумму stack1.

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

          sum1 += stack1[i];

       

      // Находим начальную сумму stack2.

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

          sum2 += stack2[i];

       

      // Находим начальную сумму stack3.

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

          sum3 += stack3[i];

       

      // Как указано в вопросе, первый элемент является верхним

      // стека

      int top1 =0, top2 = 0, top3 = 0;

      int ans = 0;

      while (true)

      {

          // Если какой-либо стек пуст

          if (top1 == n1 || top2 == n2 || top3 == n3)

             return 0;

       

          // Если сумма всех трех стеков равна.

          if (sum1 == sum2 && sum2 == sum3)

             return sum1;

           

          // Находим стек с максимальной суммой и

          // удаляем его верхний элемент.

          if (sum1 >= sum2 && sum1 >= sum3)

             sum1 -= stack1[top1++];

          else if (sum2 >= sum3 && sum2 >= sum3)

             sum2 -= stack2[top2++];

          else if (sum3 >= sum2 && sum3 >= sum1)

             sum3 -= stack3[top3++];

       }

    }

      

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

    public static void main(String[] args) 

    {

          int stack1[] = { 3, 2, 1, 1, 1 };

          int stack2[] = { 4, 3, 2 };

          int stack3[] = { 1, 1, 4, 1 };

           

          int n1 = stack1.length;

          int n2 = stack2.length;

          int n3 = stack3.length;

           

          System.out.println(maxSum(stack1, stack2, 

                               stack3, n1, n2, n3));

    }

  }

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

питон

# Программа Python для расчета максимальной суммы с равным
Сумма стека.
# Возвращает максимально возможную равную сумму трех стеков
# с удалением верхних элементов разрешено

def maxSum(stack1, stack2, stack3, n1, n2, n3):

    sum1, sum2, sum3 = 0, 0, 0

    

  # Нахождение начальной суммы в стеке1.

    for i in range(n1):

        sum1 += stack1[i]

   

  # Нахождение начальной суммы в stack2.

    for i in range(n2):

        sum2 += stack2[i]

   

  # Нахождение начальной суммы в стеке3.

    for i in range(n3):

        sum3 += stack3[i]

   

  # Как указано в вопросе, первый элемент является верхним

  Количество стеков ..

    top1, top2, top3 = 0, 0, 0

    ans = 0

    while (1):

      # Если какой-либо стек пуст

        if (top1 == n1 or top2 == n2 or top3 == n3):

            return 0

   

      # Если сумма всех трех стеков равна.

        if (sum1 == sum2 and sum2 == sum3):

            return sum1

       

      # Нахождение стека с максимальной суммой и

      # удаляя свой верхний элемент.

        if (sum1 >= sum2 and sum1 >= sum3):

            sum1 -= stack1[top1]

            top1=top1+1

        elif (sum2 >= sum3 and sum2 >= sum3):

            sum2 -= stack2[top2]

            top2=top2+1

        elif (sum3 >= sum2 and sum3 >= sum1):

            sum3 -= stack3[top3]

            top3=top3+1

   
# Управляемая программа

stack1 = [ 3, 2, 1, 1, 1 ]

stack2 = [ 4, 3, 2 ]

stack3 = [ 1, 1, 4, 1 ]

   

n1 = len(stack1)

n2 = len(stack2)

n3 = len(stack3)

   

print maxSum(stack1, stack2, stack3, n1, n2, n3)

  
# Этот код предоставлен Афзалом Ансари

C #

// C # код для поиска максимальной суммы с
// равная сумма трех стеков

using System;

  

class GFG {

  

    // Возвращает максимально возможное равное

    // сумма трех стеков с удалением

    // разрешены верхние элементы

    public static int maxSum(int[] stack1,

               int[] stack2, int[] stack3,

                   int n1, int n2, int n3)

    {

          

        int sum1 = 0, sum2 = 0, sum3 = 0;

  

        // Находим начальную сумму

        // stack1.

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

            sum1 += stack1[i];

  

        // Находим начальную сумму

        // stack2.

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

            sum2 += stack2[i];

  

        // Находим начальную сумму

        // stack3.

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

            sum3 += stack3[i];

  

        // Как указано в вопросе, сначала

        // элемент является вершиной стека ..

        int top1 = 0, top2 = 0, top3 = 0;

  

        while (true) {

              

            // Если какой-либо стек пуст

            if (top1 == n1 || top2 == n2 

                            || top3 == n3)

                return 0;

  

            // Если сумма всех трех стеков

            // равны.

            if (sum1 == sum2 && sum2 == sum3)

                return sum1;

  

            // Находим стек с максимумом

            // суммируем и удаляем его верхний элемент.

            if (sum1 >= sum2 && sum1 >= sum3)

                sum1 -= stack1[top1++];

            else if (sum2 >= sum3 && sum2 >= sum3)

                sum2 -= stack2[top2++];

            else if (sum3 >= sum2 && sum3 >= sum1)

                sum3 -= stack3[top3++];

        }

    }

  

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

    public static void Main()

    {

        int[] stack1 = { 3, 2, 1, 1, 1 };

        int[] stack2 = { 4, 3, 2 };

        int[] stack3 = { 1, 1, 4, 1 };

  

        int n1 = stack1.Length;

        int n2 = stack2.Length;

        int n3 = stack3.Length;

  

        Console.Write(maxSum(stack1, stack2,

                        stack3, n1, n2, n3));

    }

}

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

PHP

<?php
// PHP программа для расчета максимума
// сумма с равной суммой стека.

  
// Возвращает максимально возможный
// равная сумма трех стеков
// с удалением верхних элементов
// позволил

function maxSum($stack1, $stack2, $stack3

                            $n1, $n2, $n3)

{

    $sum1 = 0; $sum2 = 0; $sum3 = 0;

      

    // Находим начальную сумму stack1.

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

        $sum1 += $stack1[$i];

      

    // Находим начальную сумму stack2.

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

        $sum2 += $stack2[$i];

      

    // Находим начальную сумму stack3.

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

        $sum3 += $stack3[$i];

      

    // Как дано в вопросе,

    // первый элемент сверху

    // стека

    $top1 =0;

    $top2 = 0; 

    $top3 = 0;

    $ans = 0;

    while (1)

    {

          

        // Если какой-либо стек пуст

        if ($top1 == $n1 || $top2 == $n2 ||

                              $top3 == $n3)

            return 0;

      

        // Если сумма всех трех стеков равна.

        if ($sum1 == $sum2 && $sum2 == $sum3)

            return $sum1;

          

        // Находим стек с

        // максимальная сумма и

        // удаляем его верхний элемент.

        if ($sum1 >= $sum2 && $sum1 >= $sum3)

                $sum1 -= $stack1[$top1++];

                  

        else if ($sum2 >= $sum3 && $sum2 >=$sum3)

                $sum2 -= $stack2[$top2++];

                  

        else if ($sum3 >= $sum2 && $sum3 >= $sum1)

                $sum3 -= $stack3[$top3++];

    }

}

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

$stack1 = array(3, 2, 1, 1, 1);

$stack2 = array(4, 3, 2);

$stack3 = array(1, 1, 4, 1);

  

$n1 = sizeof($stack1);

$n2 = sizeof($stack2);

$n3 = sizeof($stack3);

echo maxSum($stack1, $stack2

            $stack3, $n1

            $n2, $n3) ;

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


Выход:

5

Сложность времени: O (n1 + n2 + n3), где n1, n2 и n3 — размеры трех стеков.

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

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

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

Найти максимально возможную сумму, равную сумме трех стеков

0.00 (0%) 0 votes