Рубрики

Максимальная сумма пути в двух массивах

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

Ожидаемая сложность по времени составляет O (m + n), где m — количество элементов в ar1 [], а n — количество элементов в ar2 [].

Примеры:

Input:  ar1[] = {2, 3, 7, 10, 12}, ar2[] = {1, 5, 7, 8}
Output: 35
35 is sum of 1 + 5 + 7 + 10 + 12.
We start from first element of arr2 which is 1, then we
move to 5, then 7.  From 7, we switch to ar1 (7 is common)
and traverse 10 and 12.

Input:  ar1[] = {10, 12}, ar2 = {5, 7, 9}
Output: 22
22 is sum of 10 and 12.
Since there is no common element, we need to take all 
elements from the array with more sum.

Input:  ar1[] = {2, 3, 7, 10, 12, 15, 30, 34}
        ar2[] = {1, 5, 7, 8, 10, 15, 16, 19}
Output: 122
122 is sum of 1, 5, 7, 8, 10, 12, 15, 30, 34

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

1) Инициализируйте результат как 0. Также инициализируйте две переменные sum1 и sum2 как 0. Здесь sum1 и sum2 используются для хранения суммы элементов в ar1 [] и ar2 [] соответственно. Эти суммы находятся между двумя общими точками.

2) Теперь выполните цикл для обхода элементов обоих массивов. При обходе сравнивайте текущие элементы ar1 [] и ar2 [].

2.a) Если текущий элемент ar1 [] меньше текущего элемента ar2 [], обновите sum1, иначе, если текущий элемент ar2 [] меньше, обновите sum2.

2.b) Если текущие элементы ar1 [] и ar2 [] совпадают, то возьмите максимум sum1 и sum2 и добавьте его к результату. Также добавьте общий элемент к результату.

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

C ++

#include<iostream>

using namespace std;

  
// Сервисная функция для поиска максимум двух целых

int max(int x, int y) { return (x > y)? x : y; }

  
// Эта функция возвращает сумму элементов на максимальном пути
// от начала до конца

int maxPathSum(int ar1[], int ar2[], int m, int n)

{

    // инициализируем индексы для ar1 [] и ar2 []

    int i = 0, j = 0;

  

    // Инициализируем результат и текущую сумму через ar1 [] и ar2 [].

    int  result = 0, sum1 = 0, sum2 = 0;

  

    // Ниже 3 цикла похожи на слияние в сортировке слиянием

    while (i < m && j < n)

    {

        // Добавить элементы ar1 [] к sum1

        if (ar1[i] < ar2[j])

            sum1 += ar1[i++];

  

        // Добавить элементы ar2 [] в sum2

        else if (ar1[i] > ar2[j])

            sum2 += ar2[j++];

  

        else  // мы достигли общей точки

        {

            // Взять максимум две суммы и добавить к результату

            result += max(sum1, sum2);

  

            // Обновляем sum1 и sum2 для элементов после этого

            // точка пересечения

            sum1 = 0, sum2 = 0;

  

            // Продолжаем обновлять результат, пока встречаются

            // элементы

            while (i < m &&  j < n && ar1[i] == ar2[j])

            {

                result = result + ar1[i++];

                j++;

            }

        }

    }

  

    // Добавить оставшиеся элементы ar1 []

    while (i < m)

        sum1  +=  ar1[i++];

  

    // Добавить оставшиеся элементы ar2 []

    while (j < n)

        sum2 +=  ar2[j++];

  

    // Добавить максимум две суммы оставшихся элементов

    result +=  max(sum1, sum2);

  

    return result;

}

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

int main()

{

    int ar1[]  = {2, 3, 7, 10, 12, 15, 30, 34};

    int ar2[] =  {1, 5, 7, 8, 10, 15, 16, 19};

    int m = sizeof(ar1)/sizeof(ar1[0]);

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

    cout << "Maximum sum path is " 

         << maxPathSum(ar1, ar2, m, n);

    return 0;

}

Джава

class MaximumSumPath 

{

    // Сервисная функция для поиска максимум двух целых

    int max(int x, int y) 

    {

        return (x > y) ? x : y;

    }

  

    // Эта функция возвращает сумму элементов на максимальном пути

    // от начала до конца

    int maxPathSum(int ar1[], int ar2[], int m, int n) 

    {

        // инициализируем индексы для ar1 [] и ar2 []

        int i = 0, j = 0;

  

        // Инициализируем результат и текущую сумму через ar1 [] и ar2 [].

        int result = 0, sum1 = 0, sum2 = 0;

  

        // Ниже 3 цикла похожи на слияние в сортировке слиянием

        while (i < m && j < n) 

        {

            // Добавить элементы ar1 [] к sum1

            if (ar1[i] < ar2[j])

                sum1 += ar1[i++];

              

            // Добавить элементы ar2 [] в sum2

            else if (ar1[i] > ar2[j])

                sum2 += ar2[j++];

  

            // мы достигли общей точки

            else

            {

                // Взять максимум две суммы и добавить к результату

                result += max(sum1, sum2);

  

                // Обновляем sum1 и sum2 для элементов после этого

                // точка пересечения

                sum1 = 0;

                sum2 = 0;

  

                // Продолжаем обновлять результат, пока встречаются

                // элементы

                while (i < m && j < n && ar1[i] == ar2[j]) 

                {

                    result = result + ar1[i++];

                    j++;

                }

            }

        }

  

        // Добавить оставшиеся элементы ar1 []

        while (i < m)

            sum1 += ar1[i++];

          

        // Добавить оставшиеся элементы ar2 []

        while (j < n) 

            sum2 += ar2[j++];

  

        // Добавить максимум две суммы оставшихся элементов

        result += max(sum1, sum2);

  

        return result;

    }

  

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

    public static void main(String[] args) 

    {

        MaximumSumPath sumpath = new MaximumSumPath();

        int ar1[] = {2, 3, 7, 10, 12, 15, 30, 34};

        int ar2[] = {1, 5, 7, 8, 10, 15, 16, 19};

        int m = ar1.length;

        int n = ar2.length;

        System.out.println("Maximum sum path is :"

                                       sumpath.maxPathSum(ar1, ar2, m, n));

    }

}

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

питон

# Python программа для поиска максимальной суммы пути

  
# Эта функция возвращает сумму элементов на максимальном пути из
# начало до конца

def maxPathSum(ar1,ar2 , m , n):

      

    # инициализировать индексы для ar1 [] и ar2 []

    i, j = 0, 0

      

    # Инициализировать результат и текущую сумму через ar1 [] и ar2 []

    result, sum1, sum2= 0, 0, 0

      

    # Ниже 3 цикла похожи на слияние в сортировке слияния

    while (i < m and j < n):

        

        # Добавить элементы ar1 [] в sum1

        if ar1[i] < ar2[j]:

            sum1 += ar1[i]

            i+=1

          

        # Добавить элементы ar2 [] в sum1

        elif ar1[i] > ar2[j]:

            sum2 += ar2[j]

            j+=1

          

        else:   # мы достигли общей точки

          

            # Взять максимум две суммы и прибавить к результату

            result+= max(sum1,sum2)

              

            # Обновление sum1 и sum2 для элементов после этой точки пересечения

            sum1, sum2 = 0, 0

              

            # Продолжайте обновлять результат, пока есть более общие элементы

            while (i < m and j < n and ar1[i]==ar2[j]):

                result += ar1[i]

                i+=1

                j+=1

      

    # Добавить оставшиеся элементы ar1 []

    while i < m:

        sum1 += ar1[i]

        i+=1

    # Добавить оставшиеся элементы b []

    while j < n:

        sum2 += ar2[j]

        j+=1

      

    # Добавить максимум две суммы оставшихся элементов

    result += max(sum1,sum2)

      

    return result

  
# Функция драйвера

ar1 = [2, 3, 7, 10, 12, 15, 30, 34]

ar2 = [1, 5, 7, 8, 10, 15, 16, 19]

m = len(ar1)

n = len(ar2)

print "Maximum sum path is", maxPathSum(ar1, ar2, m, n)

  
# Этот код предоставлен __Devesh Agrawal__

C #

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

using System;

  

class GFG {

      

    // Сервисная функция для поиска максимума

    // из двух целых

    static int max(int x, int y) 

    {

        return (x > y) ? x : y;

    }

  

    // Эта функция возвращает сумму

    // элементы на максимальном пути от

    // начало до конца

    static int maxPathSum(int []ar1, int []ar2, 

                                  int m, int n) 

    {

          

        // инициализируем индексы для ar1 []

        // и ar2 []

        int i = 0, j = 0;

  

        // Инициализируем результат и текущий

        // суммируем через ar1 [] и ar2 [].

        int result = 0, sum1 = 0, sum2 = 0;

  

        // Ниже 3 цикла похожи на

        // объединить в сортировку слиянием

        while (i < m && j < n) 

        {

            // Добавить элементы ar1 [] к sum1

            if (ar1[i] < ar2[j])

                sum1 += ar1[i++];

              

            // Добавить элементы ar2 [] в sum2

            else if (ar1[i] > ar2[j])

                sum2 += ar2[j++];

  

            // мы достигли общей точки

            else

            {

                  

                // Взять максимум два

                // суммируем и добавляем к результату

                result += max(sum1, sum2);

  

                // Обновляем sum1 и sum2 для

                // элементы после этого

                // точка пересечения

                sum1 = 0;

                sum2 = 0;

  

                // Продолжаем обновлять результат, пока

                // есть более распространенные

                // элементы

                while (i < m && j < n && 

                            ar1[i] == ar2[j]) 

                {

                    result = result + ar1[i++];

                    j++;

                }

            }

        }

  

        // Добавить оставшиеся элементы ar1 []

        while (i < m)

            sum1 += ar1[i++];

          

        // Добавить оставшиеся элементы ar2 []

        while (j < n) 

            sum2 += ar2[j++];

  

        // Добавить максимум две суммы

        // остальные элементы

        result += max(sum1, sum2);

  

        return result;

    }

  

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

    public static void Main() 

    {

        int []ar1 = {2, 3, 7, 10, 12, 15, 30, 34};

        int []ar2 = {1, 5, 7, 8, 10, 15, 16, 19};

        int m = ar1.Length;

        int n = ar2.Length;

        Console.Write("Maximum sum path is :"

                     maxPathSum(ar1, ar2, m, n));

    }

}

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

PHP

<?php
// PHP программа для поиска максимальной суммы
// Путь в двух массивах

  
// Эта функция возвращает сумму
// элементы на максимальном пути
// от начала до конца

function maxPathSum($ar1, $ar2, $m, $n)

{

      

    // инициализируем индексы для

    // ar1 [] и ar2 []

    $i = 0; 

    $j = 0;

  

    // Инициализировать результат и

    // текущая сумма через ar1 []

    // и ar2 [].

    $result = 0;

    $sum1 = 0; 

    $sum2 = 0;

  

    // ниже 3 петли похожи

    // слить в сортировку слиянием

    while ($i < $m and $j < $n)

    {

          

        // Добавить элементы

        // ar1 [] в sum1

        if ($ar1[$i] < $ar2[$j])

            $sum1 += $ar1[$i++];

  

        // Добавить элементы

        // ar2 [] to sum2

        else if ($ar1[$i] > $ar2[$j])

            $sum2 += $ar2[$j++];

  

        // мы достигли

        // общая точка

        else 

        {

              

            // Взять максимум два

            // суммируем и добавляем к результату

            $result += max($sum1, $sum2);

  

            // Обновляем sum1 и sum2 для

            // элементы после этого

            // точка пересечения

            $sum1 = 0; 

            $sum2 = 0;

  

            // Продолжаем обновлять результат, пока

            // есть более распространенные

            // элементы

            while ($i < $m and $j < $n and 

                   $ar1[$i] == $ar2[$j])

            {

                $result = $result + $ar1[$i++];

                $j++;

            }

        }

    }

  

    // Добавить оставшиеся элементы ar1 []

    while ($i < $m)

        $sum1 += $ar1[$i++];

  

    // Добавить оставшиеся элементы ar2 []

    while ($j < $n)

        $sum2 += $ar2[$j++];

  

    // Добавить максимум две суммы

    // оставшихся элементов

    $result += max($sum1, $sum2);

  

    return $result;

}

  

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

    $ar1 = array(2, 3, 7, 10, 12, 15, 30, 34);

    $ar2 = array(1, 5, 7, 8, 10, 15, 16, 19);

    $m = count($ar1);

    $n = count($ar2);

    echo "Maximum sum path is "

        , maxPathSum($ar1, $ar2, $m, $n);

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


Выход:

Maximum sum path is 122

Сложность по времени: в каждой итерации циклов while мы обрабатываем элемент из любого из двух массивов. Всего есть m + n элементов. Следовательно, временная сложность составляет O (m + n).

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

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

Максимальная сумма пути в двух массивах

0.00 (0%) 0 votes