మూడు వరుసగా లేని గరిష్ట తదుపరి మొత్తం


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది 24 * 7 ఇన్నోవేషన్ ల్యాబ్స్ యాక్సెంచర్ అమెజాన్ Delhivery పేపాల్ PayU
అర్రే డైనమిక్ ప్రోగ్రామింగ్

“వరుసగా మూడు ఉండని గరిష్ట తదుపరి మొత్తం” సమస్య మీకు ఇవ్వబడింది అమరిక of పూర్ణాంకాల. ఇప్పుడు మీరు వరుసగా మూడు అంశాలను పరిగణించలేని గరిష్ట మొత్తాన్ని కలిగి ఉన్న తదుపరిదాన్ని కనుగొనాలి. గుర్తుకు తెచ్చుకోవటానికి, తరువాతి శ్రేణి అసలు ఇన్పుట్ శ్రేణి నుండి కొన్ని మూలకాలను తీసివేసినప్పుడు మిగిలి ఉన్న శ్రేణి తప్ప మరొకటి కాదు.

ఉదాహరణ

మూడు వరుసగా లేని గరిష్ట తదుపరి మొత్తం

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

వివరణ

5 మరియు 10 లను ఎంచుకోవడానికి ఇది సులభమైన ఎంపిక. ఎందుకంటే వేరే మార్గం పెద్ద మొత్తానికి దారితీయదు.

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

వివరణ

మేము శ్రేణి మధ్యలో ఉన్న 5 ని ఎంచుకోము. ఎందుకంటే అది ప్రశ్నలో విధించిన పరిస్థితిని సంతృప్తిపరచని ఒక తదుపరితను సృష్టిస్తుంది.

అప్రోచ్

వరుసగా మూడు మూలకాలు తీసుకోబడని గరిష్ట మొత్తంతో తదుపరిదాన్ని కనుగొనమని సమస్య మమ్మల్ని కోరింది. అందువల్ల ఒక అమాయక విధానం తరువాతి తరం కావచ్చు. మునుపటి కొన్ని ప్రశ్నలలో మేము చేసినట్లు. అమాయక విధానం చాలా సమయం, తరువాతి ఫలితాలను ఉత్పత్తి చేయడానికి, తరువాత ప్రశ్నలో విధించిన పరిస్థితులను సంతృప్తి పరుస్తుందో లేదో తనిఖీ చేయండి. కానీ ఈ విధానం సమయం తీసుకుంటుంది మరియు ఆచరణాత్మకంగా ఉపయోగించబడదు. ఎందుకంటే మితమైన-పరిమాణ ఇన్పుట్ల కోసం విధానాన్ని ఉపయోగించడం సమయ పరిమితులను మించిపోతుంది. ఈ విధంగా సమస్యను పరిష్కరించడానికి మనం వేరే పద్ధతిని ఉపయోగించాలి.

మేము ఉపయోగిస్తాము డైనమిక్ ప్రోగ్రామింగ్ సమస్యను పరిష్కరించడానికి కానీ దీనికి ముందు, మేము కొన్ని కేస్‌వర్క్‌లను చేయాలి. ప్రారంభ సమస్యను చిన్న ఉపప్రాబ్లమ్‌లుగా తగ్గించడానికి ఈ కేస్‌వర్క్ జరుగుతుంది. ఎందుకంటే డైనమిక్ ప్రోగ్రామింగ్‌లో, మేము సమస్యను చిన్న ఉపప్రాబ్లమ్‌లుగా తగ్గిస్తాము. కాబట్టి, మేము ప్రస్తుత మూలకాన్ని దాటవేసినట్లు పరిగణించండి, అప్పుడు మా సమస్య మునుపటి మూలకం వరకు సమస్యను పరిష్కరించడానికి తగ్గించబడుతుంది. పరిగణించండి, మేము ప్రస్తుత మూలకాన్ని ఎంచుకుంటాము. మునుపటి మూలకం కోసం మనకు రెండు ఎంపికలు ఉన్నాయి. గాని మనం మునుపటి మూలకాన్ని ఎంచుకుంటాము, అలా చేస్తే మనం మునుపటి మూలకానికి మునుపటి మూలకాన్ని ఎన్నుకోలేము. మేము అలా చేయకపోతే, మునుపటి మూలకానికి మునుపటి వరకు సమస్యను పరిష్కరించడానికి సమస్య తగ్గించబడుతుంది. కోడ్‌ను ఉపయోగించడం అర్థం చేసుకోవడం సులభం అవుతుంది.

కోడ్

మూడు వరుసగా లేని గరిష్ట తదుపరి మొత్తాన్ని కనుగొనడానికి సి ++ కోడ్

#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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), ఎందుకంటే మేము శ్రేణిని దాటి, మా DP శ్రేణిని నింపడం కొనసాగించాము. అందువలన సమయం సంక్లిష్టత సరళంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

పై), ఎందుకంటే విలువలను నిల్వ చేయడానికి మేము ఒక డైమెన్షనల్ DP శ్రేణిని తయారు చేయాల్సి వచ్చింది. స్థల సంక్లిష్టత కూడా సరళంగా ఉంటుంది.