గరిష్ట మొత్తం పెరుగుతున్న తరువాత  


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ Atlassian బ్లూమ్బెర్గ్ ByteDance సిట్రిక్స్ కోడ్‌నేషన్ కూపాంగ్ eBay <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ IBM మైక్రోసాఫ్ట్ నాగరో ఒరాకిల్ ఉబెర్ యాహూ
అర్రే బైనరీ శోధన డైనమిక్ ప్రోగ్రామింగ్

సమస్యల నివేదిక  

“గరిష్ట మొత్తం పెరుగుతున్న తరువాతి” సమస్యలో మేము ఒక ఇచ్చాము అమరిక. ఇచ్చిన శ్రేణి యొక్క గరిష్ట తరువాతి మొత్తాన్ని కనుగొనండి, అనగా తరువాతిలోని పూర్ణాంకాలు క్రమబద్ధీకరించబడిన క్రమంలో ఉంటాయి.

తరువాతి శ్రేణి యొక్క ఒక భాగం, ఇది క్రమాన్ని మార్చకుండా కొన్ని అంశాలను తొలగించడం ద్వారా మరొక క్రమం నుండి తీసుకోబడిన క్రమం. ఈ క్రింది ఉదాహరణలో దీనిని వివరించవచ్చు.

ఉదాహరణ  

4
18 5 17 23
45

వివరణ: పై ఉదాహరణలో, 45 గరిష్ట మొత్తం. పై ఉదాహరణలో, పెరుగుతున్న రెండు పరిణామాలు ఉన్నాయి, అవి {18, 17} మరియు {5, 17, 23}. కానీ రెండవ తరువాతి గరిష్ట మొత్తాన్ని కలిగి ఉంటుంది.

అప్రోచ్  

సానుకూల సంఖ్యల శ్రేణి ఇవ్వబడింది. శ్రేణి యొక్క గరిష్ట మొత్తం తరువాతి మొత్తాన్ని మనం లెక్కించాలి, తరువాతి పెరుగుదల పెరుగుతున్న_ఆర్డర్‌లో ఉంటుంది. 

ఉదాహరణ-  [2,5,8,3,4,6]

అప్పుడు పెరుగుతున్న కొన్ని పరిణామాలు - 

[2,5,8], మొత్తం = 15

[2,8], మొత్తం = 10

[5,8], మొత్తం = 13

[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]) ఇక్కడ 0

Ans గరిష్టంగా ఉంటుంది (dp [i]) ఇక్కడ 0

అప్రోచ్  

  1. మేము క్రొత్త శ్రేణి dp ని సృష్టిస్తాము, ఇక్కడ dp [i] = a [i], ఇక్కడ 0
  2. మేము 0 <i <n నుండి బయటి లూప్‌ను నడుపుతాము.
  3. I తో ముగుస్తున్న [0, i-1] యొక్క గరిష్ట మొత్తాన్ని పెంచే ప్రతి i కోసం. [J] తో ముగుస్తున్న గరిష్ట మొత్తంతో తదుపరి పెరుగుదలను కనుగొనండి, ఇక్కడ [j] ప్రస్తుత మూలకం కంటే తక్కువగా ఉంటుంది [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-D శ్రేణిని ఉపయోగిస్తాము. ఇక్కడ మేము విలువలను సరళ dp శ్రేణిలో నిల్వ చేస్తాము.