მაქსიმალური თანმიმდევრობის ჯამი ისეთი, რომ სამი არ არის ზედიზედ


Რთული ტური საშუალო
ხშირად ეკითხებიან 24 * 7 ინოვაციის ლაბორატორია Accenture Amazon ადგილზე მიტანა PayPal პეუ
Array დინამიური პროგრამირება

პრობლემა "მაქსიმალური თანმიმდევრობის ჯამი ისეთი, რომ სამი ზედიზედ არ იყოს" აღნიშნავს, რომ თქვენ გეძლევათ მასივი of რიცხვები. ახლა თქვენ უნდა იპოვოთ თანმიმდევრობა, რომელსაც აქვს მაქსიმალური თანხა იმის გათვალისწინებით, რომ სამი ზედიზედ ელემენტს ვერ განიხილავთ. შეგახსენებთ, თანმიმდევრობა სხვა არაფერია, თუ არა მასივი, რომელიც რჩება, როდესაც ზოგიერთი ელემენტი ამოიღება საწყისი შეყვანის მასივიდან, რიგითობა შეინარჩუნებს.

მაგალითი

მაქსიმალური თანმიმდევრობის ჯამი ისეთი, რომ სამი არ არის ზედიზედ

a[] = {2, 5, 10}
50

განმარტება

ეს იყო მარტივი არჩევანი 5-ისა და 10-ის ასარჩევად, რადგან ნებისმიერი სხვა გზა არ გამოიწვევს უფრო მეტ თანხას.

a[] = {5, 10, 5, 10, 15}
40

განმარტება

ჩვენ არ ვირჩევთ 5-ს, რომელიც მასივის შუაშია. რადგან ეს შექმნის თანმიმდევრობას, რომელიც არ აკმაყოფილებს კითხვაში დაწესებულ პირობას.

მიდგომა

პრობლემამ გვთხოვა, რომ თანმიმდევრობა ვიპოვნოთ მაქსიმალური თანხით, რომ სამი ზედიზედ ელემენტი არ იყოს არჩეული. ამრიგად, გულუბრყვილო მიდგომა შეიძლება იყოს ქვესათაურების წარმოქმნა. როგორც ეს წინა კითხვებში გავაკეთეთ. გულუბრყვილო მიდგომა უმეტესად არის, ქვეპროცედების წარმოქმნა, შემდეგ შეამოწმეთ, აკმაყოფილებს თუ არა თანმიმდევრობა პირობებში, რომლებიც დაწესებულია კითხვაში. მაგრამ ეს მიდგომა შრომატევადია და მისი პრაქტიკულად გამოყენება არ შეიძლება. რადგან მიდგომის გამოყენება ზომიერი ზომის შენატანებისთვისაც კი გადააჭარბებს ვადებს. ამრიგად, პრობლემის გადასაჭრელად უნდა გამოვიყენოთ სხვა მეთოდი.

ჩვენ გამოვიყენებთ დინამიური პროგრამირება პრობლემის გადასაჭრელად, მაგრამ მანამდე უნდა შევასრულოთ საქმისწარმოება. ეს საქმისწარმოება შესრულებულია იმისათვის, რომ თავდაპირველი პრობლემა შემცირდეს მცირე ქვეპროგრამებში. იმის გამო, რომ დინამიური პროგრამირებისას, ჩვენ პრობლემას ვამცირებთ უფრო მცირე ქვეპროგრამებად. ასე რომ, ჩათვალეთ, რომ ჩვენ გამოტოვებთ მიმდინარე ელემენტს, მაშინ ჩვენი პრობლემა შემცირდება პრობლემის გადაჭრაზე წინა ელემენტამდე. განვიხილოთ, ჩვენ ვირჩევთ ამჟამინდელ ელემენტს. მაშინ წინა ელემენტისთვის გვაქვს ორი არჩევანი. ან ავირჩიოთ წინა ელემენტი, თუ ავირჩევთ, მაშინ ვერ შევძლებთ წინა ელემენტის წინა ელემენტის არჩევას. თუ ჩვენ ეს არ გაგვაჩნია, პრობლემა იკლებს პრობლემის გადაჭრას წინა ელემენტამდე. უფრო ადვილი იქნება კოდის გამოყენება.

კოდი

C ++ კოდი, რათა იპოვოთ თანმიმდევრობის მაქსიმალური თანხა, რომ სამი ზედიზედ არ იყოს

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(a) / sizeof(a[0]);
    int dp[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = max({a[0] + a[1], a[2]+a[0], a[2]+a[1]});
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = max({a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i], dp[i-1]});
    cout<<dp[n-1];
}
16

ჯავის კოდი, რათა იპოვოთ თანმიმდევრობის მაქსიმალური თანხა ისეთი, რომ სამი ზედიზედ არ იყოს

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = a.length;
    int dp[] = new int[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = Math.max(Math.max(a[0] + a[1], a[2]+a[0]), a[2]+a[1]);
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = Math.max(Math.max(a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i]), dp[i-1]);

    System.out.println(dp[n-1]);
  }
}
16

სირთულის ანალიზი

დროის სირთულე

O (N), რადგან ჩვენ უბრალოდ გადავკვეთეთ მასივი და ვაგრძელებდით ჩვენი DP მასივის შევსებას. ამრიგად, დროის სირთულე წრფივია.

სივრცის სირთულე

O (N), რადგან მნიშვნელობების შესანახად ერთგანზომილებიანი DP მასივი უნდა შეგვექმნა. სივრცის სირთულე ასევე ხაზოვანია.