Աճող հետևանքի առավելագույն արտադրանք


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակոլիտ GE Healthcare HackerRank IBM Snapchat Անտաշ անասուն նողկալի արարած
Դասավորություն Դինամիկ ծրագրավորում

Խնդիրի հայտարարություն

«Աճող հաջորդականության առավելագույն արտադրյալ» խնդիրը նշում է, որ ձեզ տրվում է ամբողջ թվերի զանգված: Այժմ դուք պետք է պարզեք առավելագույն արտադրանքը, որին կարող եք հասնել այնպես, որ բազմապատկեք աճող հետևանքի տարրերը: Պետք է նշել, որ մենք չպետք է պարզենք ամենաերկար աճող հետևանքը: Մենք կարող ենք ունենալ ավելի փոքր հետևանք, բայց այն պետք է ունենա առավելագույն արտադրանք:

Օրինակ

Աճող հետևանքի առավելագույն արտադրանք

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

Աճող հետևյալի առավելագույն արտադրյալը 10, 1000 է: Նույնիսկ եթե ամենաերկար աճող հաջորդականությունը {1, 2, 3, 4} է:

Մոտեցում

Խնդիրը հիշեցնում է Ամենաերկար աճող հետևանքները Խնդիր Այդ խնդրի փոքր փոփոխությունն այն է, որ փոխարենը գտնել ամենաերկար աճող հետևանքը: Մենք պետք է գտնենք աճող հետևանքի առավելագույն արտադրանքը:

Այսպիսով, այս խնդիրը լուծելու համար: Խնդիրը լուծելու համար մենք կարող ենք օգտագործել Brute Force մոտեցումը: Չնայած այս մեթոդը անարդյունավետ է, բայց պետք է հայտնի լինի: Այսպիսով, կոպիտ ուժի մոտեցման մեջ մենք նախ կստեղծենք բոլոր հետևյալները: Ենթածրագրեր առաջացնելուց հետո մենք ստեղծում ենք ստուգիչ գործառույթ: Ստուգիչ գործառույթում մենք ստուգում ենք արդյոք հետևյալը վավեր է: Ստուգիչ գործառույթի վավերությունը նշանակում է, որ հաջորդականությունը պետք է լինի աճող հետևանք: Դրանից հետո մենք շարունակում ենք թարմացնել աճող հետևանքներից հայտնաբերված առավելագույն ապրանքը:

Հիմա հարցն այն է, թե ինչպե՞ս մենք արդյունավետ լուծենք խնդիրը: Խնդիրն արդյունավետորեն լուծելու համար մենք օգտագործում ենք Դինամիկ ծրագրավորում: Խնդրի անցումը նույնն է, ինչ LIS- ի խնդիրը: Մեր DP զանգվածը պահպանում է առավելագույն արտադրանքը, որը կարելի է ձեռք բերել, եթե մենք հաշվի առնենք բոլոր տարրերը մինչև ընթացիկ տարրը: Եվ կա ևս մեկ պայման, որ հաջորդականությունը պետք է պարունակի ընթացիկ տարրը: Դրանից հետո DP զանգվածը հաշվարկելու համար մենք ընթացիկ տարրից դեպի մեկնարկային տարր հետընթացի ուղղությամբ վարում ենք բույն դրված օղակ: Եթե ​​մենք գտնում ենք մի տարր, որն ավելի փոքր է, քան ընթացիկ տարրը, ապա մենք թարմացնում ենք մեր պատասխանը, եթե ընթացիկ տարրը բազմապատկելով DP զանգվածի այդ ցուցանիշի տարրին, ավելի մեծ է, քան ներկայումս պահված արժեքը:

Կոդ

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

Java կոդ ՝ աճող հաջորդականության առավելագույն արտադրանքը գտնելու համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N ^ 2), քանի որ մենք օգտագործում ենք երկու տեղադրված օղակ: Մեկը, որը անցնում է բոլոր տարրերի վրայով, իսկ մյուսը `ներքին օղակը անցնում է բոլոր տարրերի վրայով մինչև ընթացիկ տարրը:

Տիեզերական բարդություն

O (N), քանի որ մենք ստեղծում ենք միաչափ DP աղյուսակ: Այսպիսով, տարածության բարդությունը գծային է: