වැඩිවන පසු විපරමක උපරිම නිෂ්පාදනය


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇසොලයිට් GE සෞඛ්යාරක්ෂණය හැකර් රැන්ක් IBM ආයතනය Snapchat යාහූ
අරා ගතික වැඩසටහන්කරණය

ගැටළු ප්රකාශය

“වැඩිවන පසු විපරමක උපරිම නිෂ්පාදිතය” යන ගැටළුවේ සඳහන් වන්නේ ඔබට පූර්ණ සංඛ්‍යාවක් ලබා දී ඇති බවයි. දැන් ඔබට වැඩි කර ගත හැකි උපරිම නිෂ්පාදිතය සොයා ගැනීමට අවශ්‍ය වන අතර එමඟින් ඔබ වැඩිවන පසු විපරමක අංග ගුණ කරයි. සැලකිල්ලට ගත යුතු කාරණය නම්, වැඩිවන වැඩිවන පසු විපරම අප විසින් සොයා නොගත යුතුය. අපට කුඩා පසු විපරමක් තිබිය හැකි නමුත් එයට උපරිම නිෂ්පාදනයක් තිබිය යුතුය.

උදාහරණයක්

වැඩිවන පසු විපරමක උපරිම නිෂ්පාදනය

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

වැඩිවන පසු විපරමක උපරිම නිෂ්පාදිතය 10, 1000 වේ. දීර් increasing තම වැඩිවන අනුක්‍රමය {1, 2, 3, 4 is වුවද.

ප්රවේශය

ගැටළුව සමාන වේ දීර් est තම වැඩිවන පසු විපරම ගැටලුව. එම ගැටළුවෙහි සුළු වෙනස් කිරීමක් නම්, වැඩිවන වැඩිවන පසු විපරම සොයා ගැනීම වෙනුවට. වැඩිවන පසු විපරමක උපරිම නිෂ්පාදිතය අප සොයා ගත යුතුය.

එබැවින්, මෙම ගැටළුව විසඳීම සඳහා. ගැටලුව විසඳීම සඳහා අපට තිරිසන් බල ප්‍රවේශය භාවිතා කළ හැකිය. මෙම ක්‍රමය අකාර්යක්ෂම වුවද දැන සිටිය යුතුය. ඉතින්, තිරිසන් බල ප්රවේශය තුළ, අපි පළමුව සියලු ප්රතිවිපාක ජනනය කරමු. පසු විපරම් උත්පාදනය කිරීමෙන් පසුව, අපි පරීක්ෂක ශ්‍රිතයක් නිර්මාණය කරමු. පරීක්ෂක ශ්‍රිතයේ දී, පසු විපරම වලංගු දැයි අපි පරීක්ෂා කරමු. පරීක්ෂක ශ්‍රිතයේ වලංගු භාවය යන්නෙන් අදහස් වන්නේ අනුප්‍රාප්තිය වැඩි වන පසු විපරමක් විය යුතු බවයි. ඊට පසු, වැඩිවන පසු විපරමෙන් සොයාගත් උපරිම නිෂ්පාදනය යාවත්කාලීන කරමින් සිටිමු.

දැන් ප්‍රශ්නය වන්නේ අප ගැටලුව කාර්යක්ෂමව විසඳන්නේ කෙසේද යන්නයි. ගැටළුව කාර්යක්ෂමව විසඳීම සඳහා අපි ඩයිනමික් ක්‍රමලේඛනය භාවිතා කරමු. ගැටලුවේ සංක්‍රාන්තිය LIS ගැටලුවට සමානය. වර්තමාන මූලද්‍රව්‍යය තෙක් සියලු මූලද්‍රව්‍ය සලකා බැලුවහොත් ලබා ගත හැකි උපරිම නිෂ්පාදනය අපගේ ඩීපී අරාව ගබඩා කරයි. තවද ඊළඟ කොන්දේසියෙහි වත්මන් මූලද්‍රව්‍යය අඩංගු විය යුතු බවට තවත් එක් කොන්දේසියක් ඇත. ඩීපී අරාව ගණනය කිරීම සඳහා අපි වත්මන් මූලද්‍රව්‍යයේ සිට ආරම්භක මූලද්‍රව්‍යය දක්වා පසුගාමී දිශාවකට කූඩු ලූපයක් ධාවනය කරමු. වත්මන් මූලද්‍රව්‍යයට වඩා කුඩා මූලද්‍රව්‍යයක් අප සොයා ගන්නේ නම්, ඩීපී අරාවෙහි ඇති දර්ශකයේ ඇති මූලද්‍රව්‍යයට වත්මන් මූලද්‍රව්‍යය ගුණ කිරීම දැනට ගබඩා කර ඇති වටිනාකමට වඩා වැඩි නම් අපි අපගේ පිළිතුර යාවත්කාලීන කරමු.

කේතය

වැඩිවන පසු විපරමක උපරිම නිෂ්පාදනය සොයා ගැනීමට C ++ කේතය

#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) අපි තනි මාන DP වගුවක් නිර්මාණය කරන නිසා. මේ අනුව අවකාශයේ සංකීර්ණතාව රේඛීය වේ.