മൂന്നും തുടർച്ചയായി ഇല്ലാത്ത പരമാവധി തുടർന്നുള്ള തുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു 24 * 7 ഇന്നൊവേഷൻ ലാബുകൾ ഓട്ടോമോട്ടീവ് ആമസോൺ ദില്ലി പേപാൽ പേ
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

“മൂന്നും തുടർച്ചയായി വരാത്ത പരമാവധി തുടർന്നുള്ള തുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ശ്രേണി 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), കാരണം ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിച്ച് ഞങ്ങളുടെ ഡിപി അറേ പൂരിപ്പിച്ചുകൊണ്ടിരുന്നു. അങ്ങനെ സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), കാരണം മൂല്യങ്ങൾ സംഭരിക്കുന്നതിന് ഞങ്ങൾക്ക് ഒരു ഡൈമൻഷണൽ ഡിപി അറേ നിർമ്മിക്കേണ്ടതുണ്ട്. സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.