अधिकतम बीमित राशि बढ़ाना  


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब वीरांगना सेब Atlassian ब्लूमबर्ग ByteDance Citrix कोडेशन कपांग ईबे Facebook गूगल आईबीएम माइक्रोसॉफ्ट नगरो ओरेकल Uber याहू
ऐरे द्विआधारी खोज गतिशील प्रोग्रामिंग

समस्या का विवरण  

"अधिकतम समवर्ती वृद्धि" समस्या में हमने एक दिया है सरणी। दिए गए सरणी के अधिकतम क्रमांक का योग ज्ञात कीजिए, बाद में पूर्णांक क्रमबद्ध क्रम में हैं।

एक क्रम एक सरणी का एक हिस्सा है जो एक क्रम है जो किसी अन्य क्रम से क्रम को बदले बिना कुछ तत्वों को हटाने से प्राप्त होता है। इसे नीचे दिए गए उदाहरण में समझाया जा सकता है।

उदाहरण  

4
18 5 17 23
45

स्पष्टीकरण: उपरोक्त उदाहरण में, 45 अधिकतम राशि है। उपर्युक्त उदाहरण में, दो बढ़ती हुई संख्याएं हैं, {18, 17} और {5, 17, 23}। लेकिन दूसरी उत्तरार्ध में अधिकतम राशि है।

दृष्टिकोण  

सकारात्मक संख्याओं की एक सरणी को देखते हुए। हमें सरणी के अधिकतम योग की गणना की गणना करनी होगी जैसे कि आगे बढ़ने की प्रवृत्ति। 

उदाहरण-  [2,5,8,3,4,6]

फिर कुछ बढ़ते हुए क्रम हैं - 

[२,५,,], राशि = १५

[२,५,,], राशि = १५

[५, sum], राशि = १३

[2,3,4,6], राशि = 15

[2,5,6], राशि = 13 इत्यादि हमें मिलने वाली अधिकतम राशि 15 है।

इस समस्या को सरल उपप्रकारों में विभाजित किया जा सकता है, जिसका अर्थ है कि इसमें ए इष्टतम सबस्ट्रक्चर। और समस्या भी है अतिव्यापी उपप्रकार अगर हम इसका पुनरावर्तन वृक्ष बनाते हैं। चूँकि समस्या में इष्टतम सबस्ट्रक्चर और ओवरलैपिंग सबप्रॉब्लम्स हैं, इसलिए समस्या का उपयोग करके हल किया जा सकता है गतिशील प्रोग्रामिंग. एक [0,1, …… n-1] को एक सरणी और dp [i] = इंडेक्स i पर समाप्त होने वाली अधिकतम योगता बढ़ रही है, जैसे कि एक [i] अंतिम तत्व है।

तब dp [i] के रूप में लिखा जा सकता है, 

dp [i] = a [i] + max (L [j]) जहां ०

Ans अधिकतम होगा (dp [i]) जहां 0

दृष्टिकोण  

  1. हम एक नई सरणी dp बनाएंगे, जहां dp [i] = a [i], जहां 0
  2. हम 0 <i <n से एक बाहरी लूप चलाएंगे।
  3. प्रत्येक के लिए जो एक [0, i-1] की अधिकतम बढ़ती संख्या को संग्रहीत करता है जो कि मेरे साथ समाप्त होता है। एक [j] के साथ समाप्त होने वाली अधिकतम राशि के साथ बढ़ती हुई कार्यक्षमता, जहां एक [j] वर्तमान तत्व a i] से कम है
  4. Dp सरणी में अधिकतम ज्ञात करें।

कार्यान्वयन  

अधिकतम वृद्धि के लिए सी ++ प्रोग्राम उप-परिणाम

#include <bits/stdc++.h>
using namespace std;

int max_sum_inc_sub(vector<int> a,int n){
  vector<int> dp(a);
  int ans = 0;
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
        dp[i] = dp[j]+a[i];
      }
    }
    ans = max(ans,dp[i]);
  }
  return ans;
}
int main() {
  int n;
  cin>>n;
  vector<int> a;
  for(int i=0;i<n;i++){
    int x;cin>>x;
    a.push_back(x);
  }
  int max_sum = max_sum_inc_sub(a,n);
  cout<<max_sum<<endl;
  return 0;
}

अधिकतम वृद्धि के परिणाम के लिए जावा कार्यक्रम

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        int ans = max_sum_inc_sub(arr,n);
        System.out.println(ans);
  }
  
  public static int max_sum_inc_sub(int[] a,int n){
        int[] dp = new int[n];
        for(int i=0;i<n;i++){
        	dp[i]=a[i];
        }
        int ans = 0;
    for(int i=1;i<n;i++){
      for(int j=0;j<i;j++){
        if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
          dp[i] = dp[j]+a[i];
        }
      }
      ans = Math.max(ans,dp[i]);
    }
    return ans;
    }

}
6
2 5 8 3 4 6
15

अधिकतम समवर्ती वृद्धि के लिए जटिलता विश्लेषण  

समय जटिलता

O (n * n) जहां n दिए गए सरणी का आकार है। यहां हम दो छोरों को चलाते हैं जो हमें द्विघात समय जटिलता की ओर ले जाते हैं।

यह भी देखें
विशिष्ट अंतर के साथ जोड़े की अधिकतम राशि

अंतरिक्ष जटिलता

पर) क्योंकि हम 1-डी सरणी का उपयोग करते हैं। यहां हम एक रैखिक डीपी सरणी में मानों को संग्रहीत करते हैं।