Maksimum Cəmi Artıran Nəticə

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Fanatics microsoft Morgan Stanley
Geyim Dinamik proqramlaşdırmaBaxılıb 25

Problem bəyanat

Sizə verilir array tam ədədi. Sizin tapşırığınız sıra içindəki maksimum cəmi ardıcıllığı, ardıcıllıqdakı nömrələrin bir sıra ilə sifariş edilməli şəkildə tapılmasıdır. sıralandı qaydada artan qaydada. Bir ardıcıllıq, bəzi elementləri başlanğıc massivindən çıxardıqda əldə etdiyimiz bir ardıcıllıqdan başqa bir şey deyildir.

misal

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

İzahat: {2, 4, 5, 10, 12} cəmi ⇒ 33. Sıralanmış vəziyyətimizi təmin etmək üçün 4 indeksi (0 əsaslı indeksləşdirmə) elementi xaricində bütün başlanğıc giriş massivini götürdük. Bu ardıcıllıq bizə ən yaxşı nəticəni verir. Hər hansı digər bir sonrakı cari məbləğdən daha az bir nəticə ilə nəticələnəcəkdir.

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

İzahat: {3, 5, 7, 20} cəmi. ⇒ 35. Burada serialın qalan hissəsini sıralanan 1 və 4-ləri çıxardıq. Sonra qalan elementlər maksimum cəmi artıran ardıcıllığı edir.

 

Maksimum Cəmi Artıran Nəticənin Alqoritmi

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.

 

Izahat

Sıralana bilən və ya ayrılmayan bir sıra tamsayı verdik. Maksimum cəmi artıran sonrakılığı tapmağa çalışırıq. Bu da artan qaydada olmalıdır. Beləliklə, bunun üçün verilən sıra ilə eyni ölçüdə bir sıra yaradacağıq. Sonra çıxışı 0-a təyin etdik. Bu çıxış dəyəri bütün elementlər arasında maksimum tapmağımıza kömək edəcəkdir.

İlk dəfə serialı keçəcəyik. İlk dəfə verdiyimiz bir sıra dəyərini yaratdığımız bir massivə kopyalamaq olacaq maxSumIS []. Bu maxSumIS [] array, vəziyyətimiz nə vaxt təmin olunsa yenilənir. Beləliklə, ilk növbədə i = 1-dən massivi keçəcəyik, çünki ilk indeksdən maxSumIS massivində istifadə edəcəyik. Bu səbəbdən ikinci döngənin dəyərini 0-dan i-yə qədər götürdük. Vəziyyəti yoxlayacağıq arr [i] arr [j] -dən böyükdürsə, və həmçinin maxSumIS [j] indiki i və j indekslərinə görə əvvəlki iki elementin cəmindən azdır. Hər iki şərt yerinə yetirilərsə, maxSumIS [i] dəyərini cari iki indeks elementinin cəminə qədər maxSumIS [j] və arr [i] kimi yeniləyirik.

Bu, maksimum cəmin ardıcıllığını yalnız artan qaydada tapmaq istədiyimizə görə, eyni zamanda iki elementi götürürük.

Bundan sonra maxSumIS massivində saxladığımız və yeniləndiyimiz bütün elementlərin maksimumunu öyrənməliyik. Bütün massivi keçə bilərik və ya istənilən funksiyanı istifadə edərək maksimum sayını tapa bilərik. Lakin maxSumIS massivinin bütün elementləri arasında maksimum sayını qaytarmalıyıq.

Maksimum Cəmi Artıran NəticəPin

Maksimum Cəmi Artıran Nəticənin Kodu

C ++ kodu

#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 kodu

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

 

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Buradan bəri xarici iç döngədən iki yuva var 0-dan n-1-ə və daxili döngə 0 üçün i. Beləliklə alqoritm çox polinomal zaman mürəkkəbliyinə malikdir. O (n)2hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

Burada problemə xətti məkan mürəkkəbliyini təmin edən n ölçülü 1D massivimiz var. O (n) hara "N" massivdəki elementlərin sayıdır.

Translate »