तीनही सलग नसल्याची जास्तीत जास्त अनुक्रम रक्कम


अडचण पातळी मध्यम
वारंवार विचारले 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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण आम्ही फक्त अ‍ॅरेचा शोध लावला होता आणि आमचा डीपी अ‍ॅरे भरत होतो. अशा प्रकारे वेळेची जटिलता रेषात्मक असते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), कारण मूल्ये साठवण्यासाठी आम्हाला एक मितीय डीपी अ‍ॅरे बनवायचा होता. जागेची जटिलता देखील रेषात्मक आहे.