വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള പരമാവധി ഉൽപ്പന്നം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് GE ഹെൽത്ത്കെയർ ഹാക്കർ റാങ്ക് ഐബിഎം Snapchat യാഹൂ
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

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

“വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള പരമാവധി ഉൽ‌പ്പന്നം” എന്ന പ്രശ്‌നം, നിങ്ങൾക്ക് ഒരു കൂട്ടം സംഖ്യകൾ നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള ഘടകങ്ങളുടെ ഗുണനം വർദ്ധിപ്പിക്കുന്ന തരത്തിൽ നിങ്ങൾക്ക് നേടാൻ കഴിയുന്ന പരമാവധി ഉൽപ്പന്നം ഇപ്പോൾ നിങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്. ശ്രദ്ധിക്കേണ്ട കാര്യം, വർദ്ധിച്ചുകൊണ്ടിരിക്കുന്ന തുടർന്നുള്ള കണ്ടെത്തലുകൾ ഞങ്ങൾ കണ്ടെത്തേണ്ടതില്ല. ഞങ്ങൾക്ക് ഒരു ചെറിയ തുടർ‌നടപടി ഉണ്ടായിരിക്കാം, പക്ഷേ അതിന് പരമാവധി ഉൽ‌പ്പന്നം ഉണ്ടായിരിക്കണം.

ഉദാഹരണം

വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള പരമാവധി ഉൽപ്പന്നം

10, 1, 1000, 2, 3, 4
10000

വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള പരമാവധി ഉൽ‌പ്പന്നം 10, 1000 ആണ്. ദൈർഘ്യമേറിയ വർദ്ധനവ് {1, 2, 3, 4 is ആണെങ്കിലും.

സമീപനം

പ്രശ്നം സമാനമാണ് ദൈർഘ്യമേറിയ വർദ്ധിച്ചുവരുന്ന തുടർച്ച പ്രശ്നം. ആ പ്രശ്‌നത്തെക്കുറിച്ചുള്ള ചെറിയ പരിഷ്‌ക്കരണം, വർദ്ധിച്ചുകൊണ്ടിരിക്കുന്ന തുടർച്ച കണ്ടെത്തുന്നതിനുപകരം. വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള പരമാവധി ഉൽപ്പന്നം ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്.

അതിനാൽ, ഈ പ്രശ്നം പരിഹരിക്കാൻ. പ്രശ്‌നം പരിഹരിക്കുന്നതിന് നമുക്ക് ബ്രൂട്ട് ഫോഴ്‌സ് സമീപനം ഉപയോഗിക്കാം. ഈ രീതി കാര്യക്ഷമമല്ലെങ്കിലും അറിയപ്പെടണം. അതിനാൽ, ബ്രൂട്ട് ഫോഴ്‌സ് സമീപനത്തിൽ, ആദ്യം ഞങ്ങൾ എല്ലാ തുടർന്നുള്ള സംഭവങ്ങളും സൃഷ്ടിക്കും. തുടർന്നുള്ളവ സൃഷ്ടിച്ചതിന് ശേഷം, ഞങ്ങൾ ഒരു ചെക്കർ ഫംഗ്ഷൻ സൃഷ്ടിക്കുന്നു. ചെക്കർ ഫംഗ്ഷനിൽ, തുടർന്നുള്ള സാധുതയുണ്ടോ എന്ന് ഞങ്ങൾ പരിശോധിക്കുന്നു. ചെക്കർ ഫംഗ്ഷന്റെ സാധുത അർത്ഥമാക്കുന്നത് തുടർന്നുള്ളത് വർദ്ധിച്ചുവരുന്ന തുടർച്ചയായിരിക്കണം എന്നാണ്. അതിനുശേഷം, വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ളതിൽ നിന്ന് കണ്ടെത്തിയ പരമാവധി ഉൽപ്പന്നം ഞങ്ങൾ അപ്‌ഡേറ്റ് ചെയ്യുന്നത് തുടരുന്നു.

പ്രശ്നം എങ്ങനെ കാര്യക്ഷമമായി പരിഹരിക്കും എന്നതാണ് ഇപ്പോൾ ചോദ്യം. പ്രശ്നം കാര്യക്ഷമമായി പരിഹരിക്കുന്നതിന്, ഞങ്ങൾ ഡൈനാമിക് പ്രോഗ്രാമിംഗ് ഉപയോഗിക്കുന്നു. പ്രശ്‌നത്തിലെ പരിവർത്തനം എൽ‌ഐ‌എസ് പ്രശ്‌നത്തിന് സമാനമാണ്. നിലവിലെ ഘടകം വരെ എല്ലാ ഘടകങ്ങളും പരിഗണിച്ചാൽ നേടാനാകുന്ന പരമാവധി ഉൽപ്പന്നം ഞങ്ങളുടെ ഡിപി അറേ സംഭരിക്കുന്നു. തുടർന്നുള്ളവയിൽ നിലവിലെ ഘടകം അടങ്ങിയിരിക്കണമെന്ന് ഒരു നിബന്ധന കൂടി ഉണ്ട്. ഡിപി അറേ കണക്കാക്കുന്നതിനായി നിലവിലെ മൂലകത്തിൽ നിന്ന് ആരംഭ ഘടകത്തിലേക്ക് ഒരു പിന്നോക്ക ദിശയിൽ ഞങ്ങൾ ഒരു നെസ്റ്റഡ് ലൂപ്പ് പ്രവർത്തിപ്പിക്കുന്നു. നിലവിലെ ഘടകത്തേക്കാൾ ചെറുതായ ഒരു ഘടകം ഞങ്ങൾ കണ്ടെത്തുകയാണെങ്കിൽ, ഡിപി അറേയിലെ ആ സൂചികയിലെ ഘടകത്തിലേക്ക് നിലവിലെ ഘടകത്തെ ഗുണിച്ചാൽ നിലവിൽ സംഭരിച്ചിരിക്കുന്ന മൂല്യത്തേക്കാൾ വലുതാണെങ്കിൽ ഞങ്ങൾ ഉത്തരം അപ്‌ഡേറ്റുചെയ്യുന്നു.

കോഡ്

വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള പരമാവധി ഉൽപ്പന്നം കണ്ടെത്തുന്നതിന് സി ++ കോഡ്

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


int maxProductOfIncreasingSubsequence(vector<int> &input){
  vector<int> dp(n);
  dp[0] = input[0];
  int ans = input[0];
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(input[j] < input[i])
        dp[i] = max(dp[i], dp[j]*input[i]);
    }
    ans = max(ans, dp[i]);
  }
  return ans;
}

int main(){
  int n;cin>>n;
  vector<int> input(n);
  for(int i=0;i<n;i++)
    cin>>input[i];

  cout<<maxProductOfIncreasingSubsequence(input);
}
6
10 1 1000 2 3 4
10000

വർദ്ധിച്ചുവരുന്ന തുടർന്നുള്ള പരമാവധി ഉൽപ്പന്നം കണ്ടെത്താനുള്ള ജാവ കോഡ്

import java.util.*;

class Main{
    static int maxProductOfIncreasingSubsequence(ArrayList<Integer> input){
    ArrayList<Integer> dp = new ArrayList<Integer>();
    dp.add(input.get(0));
    int ans = input.get(0);
    int n = input.size();
    for(int i=1;i<n;i++){
      dp.add(input.get(i));
      for(int j=0;j<i;j++){
        if(input.get(j) < input.get(i))
          dp.set(i, Math.max(dp.get(i), dp.get(j)*input.get(i)));
      }
      ans = Math.max(ans, dp.get(i));
    }
    return ans;
  }

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> input = new ArrayList<>();
    for(int i=0;i<n;i++){
      int in = sc.nextInt();
      input.add(in);
    }

    int answer = maxProductOfIncreasingSubsequence(input);
    System.out.print(answer);
  }
}
6
10 1 1000 2 3 4
10000

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

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

O (N ^ 2) കാരണം ഞങ്ങൾ രണ്ട് നെസ്റ്റഡ് ലൂപ്പുകൾ ഉപയോഗിക്കുന്നു. ഒന്ന് എല്ലാ ഘടകങ്ങൾക്കും മുകളിലൂടെയും മറ്റൊന്ന് ആന്തരിക ലൂപ്പ് നിലവിലെ മൂലകം വരെ എല്ലാ മൂലകങ്ങളിലും പ്രവർത്തിക്കുന്നു.

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

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