زیادہ سے زیادہ حصول رقم اس طرح کہ کوئی تین لگاتار نہ ہوں  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے 24 * 7 انوویشن لیبز ایکسینچر ایمیزون دہلی پے پال پی پی یو
لڑی متحرک پروگرامنگ

مسئلہ "زیادہ سے زیادہ تقویت کی رقم اس طرح کہ کوئی تین مسلسل نہیں ہیں" یہ بتاتا ہے کہ آپ کو ایک دیا جاتا ہے صف of اشارے. اب آپ کو ایک ایسا تقاضا تلاش کرنے کی ضرورت ہے جس میں زیادہ سے زیادہ رقم دی گئی ہو کہ آپ مسلسل تین عناصر پر غور نہیں کرسکتے ہیں۔ یاد کرنے کے ل a ، ایک مطابقت صرف ایک صف کے سوا کچھ نہیں ہے جب کچھ عناصر کو آرڈر کو یکساں رکھتے ہوئے اصل ان پٹ سرنی سے ہٹا دیا جاتا ہے۔

مثال کے طور پر  

زیادہ سے زیادہ حصول رقم اس طرح کہ کوئی تین لگاتار نہ ہوںپن

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

وضاحت

5 اور 10 کا انتخاب کرنا یہ ایک آسان انتخاب تھا کیونکہ کسی اور طریقے سے بھی زیادہ رقم کا نتیجہ نہیں نکلے گا۔

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

وضاحت

ہم 5 کو نہیں منتخب کرتے ہیں جو صف کے بیچ میں ہے۔ کیونکہ اس سے ایک ایسا مواقع پیدا ہوگا جو سوال میں عائد شرط کو پورا نہیں کرتا ہے۔

نقطہ نظر  

مسئلے نے ہم سے کہا ہے کہ زیادہ سے زیادہ رقم کے ساتھ اس کی پیروی کی جائے تاکہ لگاتار کوئی تین عناصر منتخب نہ ہوں۔ اس طرح ایک بولی نقطہ نظر بعد کے حص theوں کی نسل ہوسکتی ہے۔ جیسا کہ ہم نے پچھلے کچھ سوالات میں کیا ہے۔ بولی کا نقطہ نظر زیادہ تر وقت ہوتا ہے ، اس لئے کہ بعد میں تقاضوں کو پیدا کیا جا check اور پھر جانچ پڑتال کی جائے کہ آیا تقویم ان شرائط کو پورا کرتا ہے جو سوال میں عائد ہیں۔ لیکن یہ نقطہ نظر وقت طلب ہے اور عملی طور پر اسے استعمال نہیں کیا جاسکتا ہے۔ کیوں کہ اعتدال پسند سائز کے آدانوں کے لئے بھی نقطہ نظر کا استعمال وقت کی حد سے تجاوز کر جائے گا۔ اس طرح اس مسئلے کو حل کرنے کے لئے ہمیں کچھ اور طریقہ استعمال کرنے کی ضرورت ہے۔

یہ بھی دیکھتے ہیں
پہلے اور دوسرے نصف بٹس کی ایک ہی رقم کے ساتھ لمبائی بائنری ترتیب کو بھی گنیں

ہم استعمال کریں گے متحرک پروگرامنگ مسئلے کو حل کرنے کے ل but لیکن اس سے پہلے ، ہمیں کچھ کیس ورک کرنے کی ضرورت ہے۔ ابتدائی دشواری کو چھوٹے چھوٹے مسائل میں کم کرنے کے لئے یہ کیس ورک کیا جاتا ہے۔ کیونکہ متحرک پروگرامنگ میں ، ہم اس مسئلے کو چھوٹے چھوٹے مسائل میں گھٹا دیتے ہیں۔ لہذا ، غور کریں کہ ہم موجودہ عنصر کو چھوڑ دیتے ہیں تب ہمارا مسئلہ کم ہو کر اس مسئلے کو حل کرنے میں پچھلے عنصر تک ہی رہ جاتا ہے۔ غور کریں ، ہم موجودہ عنصر کو منتخب کرتے ہیں۔ پھر ہمارے پاس پچھلے عنصر کے لئے دو انتخاب ہیں۔ یا تو ہم پچھلے عنصر کو چنتے ہیں ، اگر ہم ایسا کرتے ہیں تو ہم عنصر کا انتخاب پچھلے عنصر سے نہیں کرسکتے ہیں۔ لیکن اگر ہم ایسا نہیں کرتے ہیں تو ، اس مسئلے کو حل کرنے میں کم ہو جاتا ہے جب تک کہ پچھلے عنصر سے پہلے تک نہ ہو۔ کوڈ کا استعمال کرتے ہوئے سمجھنا آسان ہوگا۔

ضابطے  

سی ++ کوڈ تاکہ زیادہ سے زیادہ تقویت کی رقم تلاش کریں تاکہ کوئی تین لگاتار نہ ہوں

#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

جاوا کوڈ زیادہ سے زیادہ حصول رقم تلاش کرنے کے ل such کہ کوئی بھی تین متواتر نہ ہو

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) ، کیونکہ ہم نے آسانی سے صف کو عبور کیا تھا اور اپنی ڈی پی سرنی کو بھرتے رہے تھے۔ اس طرح وقت کی پیچیدگی لکیری ہے۔

یہ بھی دیکھتے ہیں
مینی میکس الگورتھم

خلائی پیچیدگی

O (N) ، کیونکہ ہمیں اقدار کو ذخیرہ کرنے کے لئے ایک جہتی ڈی پی سرنی بنانی تھی۔ خلائی پیچیدگی بھی لکیری ہے۔