Минбаъд афзоиши маблағи зиёдтар


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Фараж Microsoft Morgan Stanley
тартиботи ҳарбӣ Барномарезии динамикӣ

Изҳороти мушкилот

Ба шумо як асал ададҳо. Вазифаи шумо иборат аз он аст, ки пайдоиши максималии суммаро дар массив тавре муайян намоед, ки рақамҳо дар пайдарпаӣ дар мураттаб карда шудааст тарзи афзоиши тартибот. Пас аз он ҷуз як пайдарпайие нест, ки агар мо баъзе элементҳоро аз массиви аввал хориҷ кунем, ба даст меорем.

мисол

arr[] = {2,4,5,10,1,12}
33

Шарҳ: Ҷамъи {2, 4, 5, 10, 12} ⇒ 33. Мо тамоми массиви ибтидоии вурудро ба ғайр аз унсури индекси 4 (индексатсияи 0 асосёфта) гирифтаем, то ки ҳолати мураттабгаштаи моро қонеъ гардонад. Ин пайдарпаӣ ба мо натиҷаи беҳтарин медиҳад. Ҳама гуна пайдоиши дигар ба маблағи камтар аз ҷории ҳозира оварда мерасонад.

arr[] = {3,5,7,1,20,4,12}
35

Шарҳ: Ҷамъи {3, 5, 7, 20} ⇒ 35. Дар ин ҷо мо 1 ва 4-ро нест кардем, ки қисми боқимондаро ҷобаҷо мекунад. Он гоҳ унсурҳои боқимонда пайдарҳамии афзояндаи ҳаҷмро ташкил медиҳанд.

 

Алгоритми афзоиши ҳосили афзоянда

1. Declare an array say maxSumIS as the same size as the length of an array.
2. Set the output to 0.
3. Copy each element of an array into the created array.
4. Traverse the array from i=1 to i<n(length of the array)
  Now in another loop, from j=0 to j<i,
    Check if arr[i] is greater than arr[j] and maxSumIS[i] is less than maxSumIS[j]+arr[i]N,
      Then update the value of maxSumIS[i] = maxSumIS[j] + arr[i].
5. Traverse the array, and find out the maximum of all the elements from maxSumIS and return that value.

 

Шарҳ

Мо массиви бутунеро додем, ки метавонад мураттаб карда шавад ё нашавад. Мо мекӯшем, ки пайдоиши афзояндаи маблағро ёбем. Ин бояд инчунин дар афзоиши тартибот бошад. Ҳамин тавр, мо барои он массив эҷод хоҳем кард, бо ҳамон андозаи он массиви додашуда. Пас аз он мо натиҷаро ба 0 муқаррар кардем. Ин арзиши натиҷавӣ ба мо дар ёфтани максимум дар байни ҳамаи элементҳо кӯмак хоҳад кард.

Мо массивро бори аввал убур хоҳем кард. Бори аввал барои нусхабардории арзиши массиви додашуда ба массиви сохтаамон хоҳад буд maxSumIS []. ин maxSumIS [] ҳар вақте, ки шароити мо қонеъ карда мешавад, массив нав карда мешавад. Ҳамин тавр, мо аввал массивро аз i = 1 мегузаронем, зеро индекси аввалро дар массиви maxSumIS истифода хоҳем кард. Барои ҳамин, мо танҳо арзиши даврчаи дуюмро аз 0 то i гирифтем. Мо вазъро тафтиш карданӣ ҳастем агар arr [i] аз arr [j] бузургтар бошад, ва инчунин maxSumIS [j] аз ҳисоби ду унсури қаблӣ мувофиқи индекси ҷории i ва j камтар аст. Агар ҳарду шарт иҷро карда шаванд, мо арзиши maxSumIS [i] -ро ба суммаи унсури ду индекси ҳозира ҳамчун maxSumIS [j] ва arr [i] навсозӣ мекунем.

Ин ба он хотир аст, ки мо мехоҳем пайдоиши ҳосили ҳадди аксарро танҳо бо тартиби афзоишёбанда пайдо кунем, аз ин рӯ мо ҳамзамон ду унсурро мегирем.

Пас аз ин, мо бояд ҳадди аксар унсурҳои дар массиви maxSumIS ҳифзшуда ва навкардашударо пайдо кунем. Мо метавонем тамоми массивро убур кунем ё бо истифода аз ягон функсия шумораи ҳадди аксарро пайдо кунем. Аммо ба мо лозим аст, ки шумораи максимумро дар байни ҳамаи унсурҳои массиви maxSumIS баргардонем.

Минбаъд афзоиши маблағи зиёдтар

Кодекс барои оқибати афзояндаи маблағ

Кодекси C ++

#include<iostream>
using namespace std;

int getMaximumSumIS(int arr[], int n)
{
    int i, j, output = 0;
    int maxSumIS[n];

    for ( i = 0; i < n; i++ )
        maxSumIS[i] = arr[i];

    for ( i = 1; i < n; i++ )
        for ( j = 0; j < i; j++ )
            if (arr[i] > arr[j] && maxSumIS[i] < maxSumIS[j] + arr[i])
                maxSumIS[i] = maxSumIS[j] + arr[i];

    // Take the maximum out of all the possible answers
    for ( i = 0; i < n; i++ )
        if ( output < maxSumIS[i] )
            output = maxSumIS[i];

    return output;
}
int main()
{
    int arr[] = {2,4,5,10,1,12};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Total sum of Maximum Sum Increasing Subsequence : " << getMaximumSumIS( arr, n );
    return 0;
}
Total sum of Maximum Sum Increasing Subsequence : 33

 

Кодекси Java

class MaximumSumIncreasingsubsequence
{
    public static int getMaximumSumIS(int arr[], int n)
    {
        int i, j, output = 0;
        int maxSumIS[] = new int[n];

        for (i = 0; i < n; i++)
            maxSumIS[i] = arr[i];

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && maxSumIS[i] < maxSumIS[j] + arr[i])
                    maxSumIS[i] = maxSumIS[j] + arr[i];

        // Take the maximum out of all the possible answers
        for (i = 0; i < n; i++)
            if (output < maxSumIS[i])
                output = maxSumIS[i];

        return output;
    }
    public static void main(String args[])
    {
        int arr[] = {2,4,5,10,1,12};
        int n = arr.length;
        System.out.println("Total sum of Maximum Sum Increasing Subsequence : "+getMaximumSumIS(arr, n));
    }
}
Total sum of Maximum Sum Increasing Subsequence : 33

 

Таҳлили мураккабӣ

Мураккабии вақт

Азбаски дар ин ҷо мо ду ҳалқаи лона дорем, ҳалқаи берунӣ аз 0 то n-1 ва ҳалқаи ботинӣ аз 0 ба i. Ҳамин тариқ, алгоритм мураккабии вақти полиномӣ дорад. О (н2ки дар "Н" шумораи унсурҳои массив аст.

Мураккабии фазо

Дар ин ҷо, мо танҳо 1D массиви андозаи n дорем, ки мушкилии фазоии хатиро ба масъала мусоидат мекунад. Эй (н) ки дар "Н" шумораи унсурҳои массив аст.