Հաջորդականության առավելագույն գումարն այնպիսին է, որ երեքը անընդմեջ չեն


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են 24 * 7 նորարարության լաբորատորիաներ Accenture Amazon Առաքում PayPal PayU
Դասավորություն Դինամիկ ծրագրավորում

«Հաջորդականության առավելագույն գումարն այնպիսին է, որ երեքը անընդմեջ չեն» խնդիրը ասում է, որ ձեզ տրվում է դասավորություն 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

Java կոդ ՝ առավելագույն հաջորդականության գումար գտնելու համար, որպեսզի ոչ մեկը երեքը հաջորդի

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք պարզապես անցել էինք զանգվածը և շարունակում էինք լրացնել մեր DP զանգվածը: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

ՎՐԱ), քանի որ արժեքները պահելու համար մենք ստիպված էինք կազմել միաչափ DP զանգված: Տիեզերական բարդությունը նույնպես գծային է: