حداکثر مجموع دنباله به گونه ای که هیچ سه متوالی نیستند  


سطح دشواری متوسط
اغلب در 24 * 7 آزمایشگاه نوآوری Accenture آمازون تحویل کالا پی پال PayU
صف برنامه نویسی پویا

مسئله "حداکثر مبلغ ثانویه به گونه ای که هیچ سه متوالی نباشد" بیان می کند که به شما یک عدد داده می شود صف of عدد صحیح. اکنون باید دنباله ای را پیدا کنید که حداکثر مجموع را داشته باشد زیرا شما نمی توانید سه عنصر متوالی را در نظر بگیرید. برای یادآوری ، دنباله چیزی نیست جز آرایه ای که وقتی برخی از عناصر از آرایه ورودی اصلی برداشته می شوند و ترتیب را یکسان می کنند ، باقی می ماند.

مثال  

حداکثر مجموع دنباله به گونه ای که هیچ سه متوالی نیستندسنجاق

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

توضیح

این انتخاب آسان برای انتخاب 5 و 10 بود زیرا هر روش دیگری منجر به مبلغ بیشتری نمی شود.

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

توضیح

ما 5 که در وسط آرایه است را انتخاب نمی کنیم. زیرا این امر فرعی ایجاد می کند که شرایط تحمیل شده در سوال را برآورده نمی کند.

روش  

این مشکل از ما خواسته است که دنباله را با حداکثر جمع به گونه ای پیدا کنیم که سه عنصر متوالی انتخاب نشود. بنابراین یک رویکرد ساده لوحانه می تواند تولید عواقب بعدی باشد. همانطور که در برخی از س questionsالات قبلی انجام داده ایم. رویکرد ساده لوحانه بیشتر اوقات ، برای ایجاد زیرشاخه ها و سپس بررسی اینکه آیا دنباله شرایطی را که در سوال تحمیل شده است ، برآورده می کند. اما این روش وقت گیر است و به طور عملی قابل استفاده نیست. زیرا استفاده از روش حتی برای ورودی های با اندازه متوسط ​​از محدودیت های زمانی فراتر خواهد رفت. بنابراین برای حل مشکل باید از روش دیگری استفاده کنیم.

همچنین مشاهده کنید
توالی های باینری را با طول یکسان و با همان بیت های نیمه اول و دوم بشمارید

ما استفاده خواهیم کرد برنامه نویسی پویا برای حل مسئله اما قبل از آن ، ما باید برخی از کارهای قضایی را انجام دهیم. این پرونده برای کاهش مشکل اولیه به زیرمشکلات کوچکتر انجام می شود. زیرا در برنامه نویسی پویا ، مسئله را به زیرمشکلات کوچکتر کاهش می دهیم. بنابراین ، در نظر بگیرید که ما از عنصر فعلی صرف نظر می کنیم و سپس مشکل ما تا حل عنصر قبلی به حل مسئله کاهش می یابد. در نظر بگیرید ، ما عنصر فعلی را انتخاب می کنیم. سپس دو گزینه برای عنصر قبلی داریم. در صورت انتخاب عنصر قبلی ، اگر این کار را انجام دهیم نمی توانیم عنصر قبلی را به عنصر قبلی انتخاب کنیم. اما اگر این کار را نکنیم ، مشکل تا حل قبلی تا عنصر قبلی کاهش می یابد. درک استفاده از کد آسان تر خواهد بود.

رمز  

کد ++ 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

تحلیل پیچیدگی  

پیچیدگی زمان

بر)، زیرا ما به راحتی آرایه را رد کرده بودیم و به پر کردن آرایه DP خود ادامه می دادیم. بنابراین پیچیدگی زمان خطی است.

همچنین مشاهده کنید
الگوریتم MiniMax

پیچیدگی فضا

بر)، زیرا برای ذخیره مقادیر باید یک آرایه DP یک بعدی درست می کردیم. پیچیدگی فضا نیز خطی است.