Μεγιστη αυξουσα υπακολουθια με Κ εξαιρεσεις

[elenaaaa]

Καλησπέρα!

Έχω για μα εργασία να βρω την μέγιστη αύξουσα υπακολουθία (όχι συνεχόμενη) και έχω την δυνατότητα να κάνω μέχρι Κ εξαιρέσεις. Κατάφερα να το γράψω και να τρέχει με μέχρι 1 εξαίρεση. Αλλά δεν μπροώ να καταλάβω τι αλλαγή να κάνω για παραπάνω εξαιρέσεις.

Παραθέτω κ τον κώδικά μου:

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

#include <stack>

using namespace std;

vector<long int> tail;

vector<long int> bob_increasing(1,1);

vector<long int> bob_decreasing;

vector<long int> v;

int binary1(vector<long int>& v, long int l, long int r, long int key)

{

while (r - l > 1) {

long int m = l + (r - l) / 2;

if (v[m] >= key)

r = m;

else

l = m;

}

return r;

}

int LIS(vector<long int>& v)

{

if (v.size() == 0)

return 0;

vector<long int> tail(v.size(), 0);

int length = 1; // always points empty slot in tail

tail[0] = v[0];

for (int i = 1; i < v.size(); i++) {

if (v[i] < tail[0])

tail[0] = v[i];

else if (v[i] > tail[length - 1])

tail[length++] = v[i];

else

tail[binary1(tail, -1, length - 1, v[i])] = v[i];

bob_increasing.push_back(length);

}

}

int binary2(vector<long int>& v, long int l, long int r, long int key)

{

while (r - l > 1) {

long int m = l + (r - l) / 2;

if (v[m] <= key)

r = m;

else

l = m;

}

return r;

}

int LDS(vector<long int>& v)

{

if (v.size() == 0)

return 0;

vector<long int> tail(v.size(), 0);

int length = 1; // always points empty slot in tail

tail[0] = v[v.size()-1];

for (int i = v.size()-1; i >=0; i--) {

if (v[i] > tail[0])

tail[0] = v[i];

else if (v[i] < tail[length - 1])

tail[length++] = v[i];

else

tail[binary2(tail, -1, length - 1, v[i])] = v[i];

bob_decreasing.push_back(length);

}

}

int main(){

long int N,k;

ios_base::sync_with_stdio(false);

cin >> N;

for(int i=0;i<N;i++){

cin >> k;

v.push_back(k);

}

for (int i=0;i<v.size();i++){

tail.push_back(0);

}

LIS(v);

LDS(v);

long int max=1;

long int bob_size=bob_increasing.size();

for (int i=1;i<bob_size;i++){

if(bob_increasing[i-1]+bob_decreasing[bob_size-1-i] > max)

max = bob_increasing[i-1]+bob_decreasing[bob_size-1-i];

}

cout << max << '\n';

}

 

[Kercyn]

Τι ακριβώς εννοείς εξαιρέσεις;

[PC_MAGAS]

Για την μέγιστη βοήθεια θα βόλευε να μας εξηγήσεις:

1. Τι εννοείς με τον όρο υπακολουθία;
2. Πότε μια υπακολουθία είναι αύξουσα;
3. Πότε μια υπακολουθία είναι μέγιστη αύξουσα;

Ακόμα πότε μια υπακολουθία έχει εξαιρέσεις; Επιπλέον, κάτσε και περίγραψε όχι ντε και καλά εδώ αλλα σε έναν συμφοιτητή σου, σε μια πλαστική πάπια, στο κατοικήδιό σου, στον husbando/waifu σου ή στον πραγματικό σου σύντροφο:

1. Τι μορφή θα έχει αυτό που θες να κάνεις πως θα λειτουργεί.
2. Τι σημαίνει το λειτουργεί; τι προϋποθέσεις πρέπει να πληρεί μαι ορθή λειτουργία.
3. Τι σγάλμα έχεις και πως δημιουργείτε αυτό το σφάλμα

Ακόμη με ένα παράδειγμα σε χαρτί και μολύβι, ίσως να είναι χρήσιμο, ακόμη ίσως να δεις το ότι βρήκες την λύση μόνος/νη σου εάν μπορέσεις και περιγράψεις ρητά τον ορισμό για τον καθένα. Μάλλιστα στην slang των προγραμματιστών αυτό λέγετε και rubber ducking (εξ' ου και ανέφερα πλαστική πάπια).

Βάση μιας ανάγνωσης του κώδικά σου από ότι κατάλαβα προσπαθείς να βρεις το μέγιστο από μια ακολουθία δωσμένη από τον χρήστη.  Πχ. εάν δώσεις 10,2,-1,33,1877,12 θα πρέπει το αποτέλεσμα να είναι το 1877. Σωστά;
 

Ακόμη παρόλο που δεν ζητήσες, επέτρεψέ μου να κάνω κάποιες παρατηρήσεις με απότερο σκοπό την βελτίωση σου στην γραφή κώδικα:

1. Ο κώδικάς σου δεν είναι ωραία μορφοποιημένος ως εκ τούτου είναι κάπως δυσανάγνωστος, παρόλο που είναι σχετικά απλός. Έχοντας σωστά spaces (επέτρεψε το IDE σου να στο φορμάρει το VSCode και στο VSCodium μπορείς να το κάνεις σε Ubuntu με Ctrl+I) 
2. Πρώτων τα ονόματα των μεταβλητών είναι πολύ μικρά για να κατανοήσεις τον σκοπό ύπαρξης. Πχ. η μεταβλητή: ` long int N;` με το που την δει κάποιος αλεξιπτωτηστής θα κατανοήσει τι κάνει. Μην τσιγκουνέυεσε τα γράμματα.
3. Ο σκοπός του να έχεις τα vectors σε global variables τι αποσκοπείς γιατί ήθελες να έχεις αυτές τις μεταβλητές διαθέσιμες από κάθε function; Καλύτερα να το αποφεύγεις και να εφαρμόζεις το λεγόμενο immutable, δηλαδή κάθε function να μην εππηρεάζει άμεσα τα αντικείμενα (vectors, objects κλπ κλπ) εισόδου αλλά σε ένα αντίγραφο αυτών.  Λόγο ότι θα μπορείς να χάσεις εύκολα τον έλεγχο. Συγγεκριμένα οι functions:

   int LIS(vector<long int> &v)
   int LDS(vector<long int> &v)

   Θα μπορούσαν κάλλιστα να επιστρέφουν vectors αντί για int. Ακόμη δε το επιστρεφόμενο Int δεν αξιοποιείτε κάπου, άρα μήπως δεν χρειάζεστε να επιστρέφει integer; Εάν πιστεύεις πως χρειάζετε βάλε comment εξηγώντας το γιατί.

4. Ακόμη βάση αυτής της απάντησης του stackoverflow καλό είναι να μην χρησιμοποιείς το:

   using namespace std;

   Αντ΄ αυτού χρησιμοποίσέ το ως εξής: `std::cin` και `std::cout`.  Tο std είναι ένα λεγόμενο namespace, δηλαδή ένας τρόπος να αποφεύγεις να μπερδεύονται functions και Κλάσεις με το ίδιο όνομα.

5. Ακόμη, όπως και με τις μεταβλητές έτσι και με τις μεθόδους μην τσιγκουνεύεσαι στην περιγραφή. Συγγεκριμένα οι functions:
    

   int binary1(vector<long int> &v, long int l, long int r, long int key)
   int binary2(vector<long int> &v, long int l, long int r, long int key)

   Δεν είναι περιγραφικές αρκετά για να κατανοήσει ο άλλος τι κάνουν. Δες στην ονοματοδοσία μεταβλητών και συναρτήσεων, σαν ένα συνοπτικό τίτλο της χρήσης και του λόγου ύπαρξής τους.

Ελπίζω παρόλο που δεν σου έδωσα άμεσα τη λύση να σου έδωσα μεθόδους για να έλθεις ποιο κοντά σε αυτήν.

Επεξ/σία 28 Δεκεμβρίου 2019 από PC_MAGAS

[k33theod]

1 ώρα πριν, PC_MAGAS είπε

Για την μέγιστη βοήθεια θα βόλευε να μας εξηγήσεις:

1. Τι εννοείς με τον όρο υπακολουθία;
2. Πότε μια υπακολουθία είναι αύξουσα;
3. Πότε μια υπακολουθία είναι μέγιστη αύξουσα;

 

Στα αγγλικά το έψαξες; 😄

https://en.wikipedia.org/wiki/Longest_increasing_subsequence

https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

Το δεύτερο λινκ έχει και λύσεις σε μερικές γλώσσες προγραμματισμού. Τα exceptions τώρα 🙄