വർദ്ധിക്കുന്ന തുടർന്നുള്ള തുക  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ അത്ലഷിഅന് ബ്ലൂംബർഗ് ബൈറ്റ്ഡാൻസ് ക്സെൻ കോഡ്നേഷൻ കൂപാംഗ് ബെ ഫേസ്ബുക്ക് ഗൂഗിൾ ഐബിഎം മൈക്രോസോഫ്റ്റ് നാഗാരോ ഒറാക്കിൾ യൂബർ യാഹൂ
അറേ ബൈനറി തിരയൽ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

പ്രശ്നം പ്രസ്താവന  

“പരമാവധി തുക വർദ്ധിക്കുന്ന തുടർ‌ന്നുള്ള” പ്രശ്‌നത്തിൽ‌ ഞങ്ങൾ‌ ഒരു നൽകി ശ്രേണി. തന്നിരിക്കുന്ന അറേയുടെ പരമാവധി തുടർച്ചയുടെ ആകെത്തുക കണ്ടെത്തുക, അതായത് തുടർന്നുള്ള സംഖ്യകൾ അടുക്കിയ ക്രമത്തിലാണ്.

ക്രമം മാറ്റാതെ ചില ഘടകങ്ങൾ ഇല്ലാതാക്കിക്കൊണ്ട് മറ്റൊരു ശ്രേണിയിൽ നിന്ന് ഉരുത്തിരിഞ്ഞ ഒരു ശ്രേണിയാണ് ഒരു തുടർച്ച. ചുവടെയുള്ള ഉദാഹരണത്തിൽ ഇത് വിശദീകരിക്കാം.

ഉദാഹരണം  

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

ഉത്തരം പരമാവധി 0 (dp [i]) ആയിരിക്കും XNUMX

സമീപനം  

  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 നൽകിയ അറേയുടെ വലുപ്പമാണ്. ക്വാഡ്രാറ്റിക് സമയ സങ്കീർണ്ണതയിലേക്ക് നയിക്കുന്ന ലൂപ്പുകൾക്കായി ഇവിടെ ഞങ്ങൾ രണ്ട് നെസ്റ്റഡ് പ്രവർത്തിപ്പിക്കുന്നു.

ഇതും കാണുക
നിർദ്ദിഷ്ട വ്യത്യാസമുള്ള ജോഡികളുടെ പരമാവധി തുക

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

O (n) കാരണം ഞങ്ങൾ 1-D അറേ ഉപയോഗിക്കുന്നു. ഇവിടെ ഞങ്ങൾ ഒരു ലീനിയർ ഡിപി അറേയിൽ മൂല്യങ്ങൾ സംഭരിക്കുന്നു.