Рубрики

Максимальная сумма увеличения подпоследовательности | DP-14

Динамическое программирование, Массивы

Дан массив из n натуральных чисел. Напишите программу, чтобы найти сумму максимальной суммы подпоследовательности данного массива так, чтобы целые числа в подпоследовательности сортировались в порядке возрастания. Например, если input равен {1, 101, 2, 3, 100, 4, 5}, то выходной сигнал должен быть 106 (1 + 2 + 3 + 100), если входной массив равен {3, 4, 5, 10 }, то на выходе должно быть 22 (3 + 4 + 5 + 10), а если входной массив равен {10, 5, 4, 3}, то на выходе должно быть 10

Решение
Эта проблема представляет собой вариант стандартной задачи с наибольшей возрастающей подпоследовательностью (LIS) . Нам нужно немного изменить решение задачи LIS в динамическом программировании. Все, что нам нужно изменить, это использовать сумму в качестве критерия вместо длины возрастающей подпоследовательности.

Ниже приведено динамическое программирование решения проблемы:

C ++

/ * Реализация динамического программирования
подпоследовательности увеличения максимальной суммы
(MSIS) проблема * /
#include <bits/stdc++.h>

using namespace std;

  
/ * maxSumIS () возвращает максимум
сумма возрастающей подпоследовательности
в обр [] размером n * /

int maxSumIS(int arr[], int n) 

{ 

    int i, j, max = 0; 

    int msis[n]; 

  

    / * Инициализировать значения msis

    для всех индексов * /

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

        msis[i] = arr[i]; 

  

    / * Вычислить максимальные значения суммы

    в восходящем порядке * /

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

        for ( j = 0; j < i; j++ ) 

            if (arr[i] > arr[j] && 

                msis[i] < msis[j] + arr[i]) 

                msis[i] = msis[j] + arr[i]; 

  

    / * Выберите максимум

    все значения msis * /

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

        if ( max < msis[i] ) 

            max = msis[i]; 

  

    return max; 

} 

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

int main() 

{ 

    int arr[] = {1, 101, 2, 3, 100, 4, 5}; 

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

    cout << "Sum of maximum sum increasing "

            "subsequence is " << maxSumIS( arr, n ) << endl; 

    return 0; 

} 

  
// Это код, предоставленный rathbhupendra

С

/ * Реализация динамического программирования
подпоследовательности увеличения максимальной суммы
(MSIS) проблема * /
#include<stdio.h>

  
/ * maxSumIS () возвращает максимум

   сумма возрастающей подпоследовательности

   в обр [] размером n * /

int maxSumIS(int arr[], int n)

{

    int i, j, max = 0;

    int msis[n];

  

    / * Инициализировать значения msis

       для всех индексов * /

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

        msis[i] = arr[i];

  

    / * Вычислить максимальные значения суммы

       в восходящем порядке * /

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

        for ( j = 0; j < i; j++ )

            if (arr[i] > arr[j] && 

                msis[i] < msis[j] + arr[i])

                msis[i] = msis[j] + arr[i];

  

    / * Выберите максимум

       все значения msis * /

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

        if ( max < msis[i] )

            max = msis[i];

  

    return max;

}

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

int main()

{

    int arr[] = {1, 101, 2, 3, 100, 4, 5};

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

    printf("Sum of maximum sum increasing " 

            "subsequence is %d\n",

              maxSumIS( arr, n ) );

    return 0;

}

Джава

/ * Динамическое программирование Java

   реализация максимальной суммы

   Увеличивающаяся подпоследовательность (MSIS)

   проблема * /

class GFG

{

    / * maxSumIS () возвращает

    максимальная сумма увеличения

    подпоследовательность в arr [] размера n * /

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

    {

        int i, j, max = 0;

        int msis[] = new int[n];

  

        / * Инициализировать значения msis

           для всех индексов * /

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

            msis[i] = arr[i];

  

        / * Вычислить максимальные значения суммы

           в восходящем порядке * /

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

            for (j = 0; j < i; j++)

                if (arr[i] > arr[j] &&

                    msis[i] < msis[j] + arr[i])

                    msis[i] = msis[j] + arr[i];

  

        / * Выберите максимум из всех

           значения мсис * /

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

            if (max < msis[i])

                max = msis[i];

  

        return max;

    }

  

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

    public static void main(String args[])

    {

        int arr[] = new int[]{1, 101, 2, 3, 100, 4, 5};

        int n = arr.length;

        System.out.println("Sum of maximum sum "+

                            "increasing subsequence is "+

                              maxSumIS(arr, n));

    }

}

  
// Этот код добавлен
// Раджат Мишра

питон

# Динамическое программирование bsed Python
# реализация максимальной суммы
# Увеличение подпоследовательности (MSIS)
# проблема

  
# maxSumIS () возвращает максимум
# сумма возрастающей подпоследовательности
# в обр [] размера n

def maxSumIS(arr, n):

    max = 0

    msis = [0 for x in range(n)]

  

    # Инициализировать значения msis

    # для всех индексов

    for i in range(n):

        msis[i] = arr[i]

  

    # Рассчитать максимальную сумму

    # значения снизу вверх

    for i in range(1, n):

        for j in range(i):

            if (arr[i] > arr[j] and

                msis[i] < msis[j] + arr[i]):

                msis[i] = msis[j] + arr[i]

  

    # Выберите максимум

    # все значения msis

    for i in range(n):

        if max < msis[i]:

            max = msis[i]

  

    return max

  
Код водителя

arr = [1, 101, 2, 3, 100, 4, 5]

n = len(arr)

print("Sum of maximum sum increasing " + 

                     "subsequence is " +

                  str(maxSumIS(arr, n)))

  
# Этот код добавлен
# Бхавья Джайн

C #

// Динамическое программирование C # реализация
// подпоследовательности увеличения максимальной суммы
// (MSIS) проблема

using System;

class GFG {

      

    // maxSumIS () возвращает

    // максимальная сумма увеличения

    // подпоследовательность в arr [] размера n

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

    {

        int i, j, max = 0;

        int []msis = new int[n];

  

        / * Инициализировать значения msis

           для всех индексов * /

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

            msis[i] = arr[i];

  

        / * Вычислить максимальные значения суммы

           в восходящем порядке * /

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

            for ( j = 0; j < i; j++ )

                if ( arr[i] > arr[j] &&

                    msis[i] < msis[j] + arr[i])

                    msis[i] = msis[j] + arr[i];

  

        / * Выберите максимум из всех

           значения мсис * /

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

            if ( max < msis[i] )

                max = msis[i];

  

        return max;

    }

      

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

    public static void Main()

    {

        int []arr = new int[]{1, 101, 2, 3, 100, 4, 5};

        int n = arr.Length;

        Console.WriteLine("Sum of maximum sum increasing "+

                                        " subsequence is "+

        maxSumIS(arr, n));

    }

}

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

PHP

<?php
// Динамическое программирование реализации
// увеличения максимальной суммы
// Подпоследовательность (MSIS) проблема

  
// maxSumIS () возвращает максимум
// сумма возрастающей подпоследовательности
// в arr [] размера n

function maxSumIS($arr, $n)

{

    $max = 0;

    $msis= array($n);

  

    // Инициализируем значения msis

    // для всех индексов

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

        $msis[$i] = $arr[$i];

  

    // Вычисляем максимальные значения суммы

    // снизу вверх

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

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

            if ($arr[$i] > $arr[$j] && 

                $msis[$i] < $msis[$j] + $arr[$i])

                $msis[$i] = $msis[$j] + $arr[$i];

  

    // Выбрать максимум всех значений msis

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

        if ($max < $msis[$i] )

            $max = $msis[$i];

  

    return $max;

}

  

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

    $arr = array(1, 101, 2, 3, 100, 4, 5);

    $n = count($arr);

    echo "Sum of maximum sum increasing subsequence is " 

                                   .maxSumIS( $arr, $n );

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

Выход :

Sum of maximum sum increasing subsequence is 106

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

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

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

Максимальная сумма увеличения подпоследовательности | DP-14

0.00 (0%) 0 votes