Μέγιστο προϊόν με αυξανόμενη ακολουθία


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Απολύτως GE Healthcare HackerRank IBM Snapchat Yahoo
Παράταξη Δυναμικός προγραμματισμός

Δήλωση προβλήματος

Το πρόβλημα "Μέγιστο προϊόν με αυξανόμενη ακολουθία" δηλώνει ότι σας δίνεται μια σειρά ακέραιων αριθμών. Τώρα πρέπει να μάθετε το μέγιστο προϊόν που μπορείτε να επιτύχετε έτσι ώστε να πολλαπλασιάζετε τα στοιχεία μιας αυξανόμενης ακολουθίας. Αυτό που πρέπει να σημειωθεί είναι ότι, δεν υποτίθεται ότι θα ανακαλύψουμε τη μεγαλύτερη αυξανόμενη ακολουθία. Μπορεί να έχουμε μικρότερη ακολουθία, αλλά θα πρέπει να έχει το μέγιστο προϊόν.

Παράδειγμα

Μέγιστο προϊόν με αυξανόμενη ακολουθία

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

Το μέγιστο προϊόν μιας αυξανόμενης ακολουθίας είναι 10, 1000. Ακόμα κι αν η μεγαλύτερη αυξανόμενη ακολουθία είναι {1, 2, 3, 4}.

Προσέγγιση

Το πρόβλημα μοιάζει με το Μεγαλύτερη αυξανόμενη ακολουθία Πρόβλημα. Η μικρή τροποποίηση αυτού του προβλήματος είναι ότι αντί να βρούμε τη μεγαλύτερη αυξανόμενη ακολουθία. Πρέπει να βρούμε το μέγιστο προϊόν μιας αυξανόμενης ακολουθίας.

Έτσι, για να λυθεί αυτό το πρόβλημα. Μπορούμε να χρησιμοποιήσουμε την προσέγγιση Brute Force για να λύσουμε και το πρόβλημα. Παρόλο που αυτή η μέθοδος είναι αναποτελεσματική αλλά πρέπει να είναι γνωστή. Έτσι, στην προσέγγιση ωμής βίας, θα δημιουργήσουμε πρώτα όλες τις ακολουθίες. Μετά τη δημιουργία των ακολουθιών, δημιουργούμε μια συνάρτηση πούλι. Στη συνάρτηση πούλι, ελέγχουμε αν η αλληλουχία είναι έγκυρη. Η εγκυρότητα της συνάρτησης πούλι σημαίνει ότι η ακολουθία πρέπει να είναι μια αυξανόμενη ακολουθία. Μετά από αυτό, συνεχίζουμε να ενημερώνουμε το μέγιστο προϊόν που βρέθηκε από την αυξανόμενη ακολουθία.

Τώρα το ερώτημα είναι πώς επιλύουμε το πρόβλημα αποτελεσματικά; Για την αποτελεσματική επίλυση του προβλήματος, χρησιμοποιούμε το Dynamic Programming. Η μετάβαση στο πρόβλημα είναι η ίδια με εκείνη του προβλήματος 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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

O (N ^ 2) επειδή χρησιμοποιούμε δύο ένθετους βρόχους. Ένα που τρέχει πάνω από όλα τα στοιχεία και ο άλλος εσωτερικός βρόχος τρέχει πάνω από όλα τα στοιχεία μέχρι το τρέχον στοιχείο.

Διαστημική πολυπλοκότητα

O (N) επειδή δημιουργούμε έναν μονοδιάστατο πίνακα DP. Έτσι, η διαστημική πολυπλοκότητα είναι γραμμική.