የከፍተኛው ቀጣይ ድምር ሦስቱ ተከታታይ እንዳይሆኑ  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ 24 * 7 የፈጠራ ላብራቶሪዎች Accenture አማዞን አቅርቦት የ 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

የጃቫ ኮድ ከፍተኛውን የተከታታይ ድምር ለማግኘት ሦስቱ ተከታታይ አይደሉም

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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም እኛ በቀላሉ ድርደራውን ተሻግረን የዲ ፒ ድርደራችንን መሙላታችንን ቀጠልን። ስለዚህ የጊዜ ውስብስብነት መስመራዊ ነው።

ተመልከት
ሚኒማክስ አልጎሪዝም

የቦታ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም እሴቶቹን ለማከማቸት አንድ ልኬት የዲፒ ድርድር ማድረግ ነበረብን ፡፡ የቦታ ውስብስብነት እንዲሁ መስመራዊ ነው።