Μέγιστο σε γραμμικό χρόνο

[Anubis13]

Καλησπέρα,

 

έχω ένα μονοδιάστατο πίνακα έστω Α={10 1 9 9 1 10 1 1 1} και θέλω να βρω πότε το A+A[j] + i - j μεγιστοποιείται σε γραμμικό χρόνο. Βλέπω την πιθανή λύση του Ν^2. Μήπως έχει κάποιος ιδέα για κάτι γραμμικό?

[tr3quart1sta]

τι εννοεις με

 

A+A[j] + i - j

??

[geomagas]

Εντελώς πρόχειρα, δεν το πολυσκέφτηκα:

 

Το A+A[j] + i - j δεν μεγιστοποιείται όταν μεγιστοποιείται το Α[k]+k;

Εννοώ, αφού ο πίνακας είναι μονοδιάστατος.

[Anubis13]

Για τον πινακα που εδωσα το max ειναι A[2] + A[3] + i - j αλλά προσοχή αν το δω κυκλικά το i - j μεγιστοποιείται στο 8

αρα εχω 9+9+8=26

[albNik]

Φτιαξε ενα πινακα με τα A+i και ενα δευτερο με τα A-i. Βρες το αθροισμα των 2 max που δεν ειναι στην ιδα θεση

[Anubis13]

Δεν την καταλαβα την ιδεα σου. Μου δινεις ενα παραδειγμα?

[albNik]

A+A[j]+i-j = (A+i) + (A[j]-j) 

θες το μεγαλυτερο A+i , και το μεγαλυτερο A[j]-j  (τα οποια βρισκεις σε γραμμικο χρονο).

 

EDit

Αλλα δεν σου κανει για το κυκλικο παραδειγμα.

[Anubis13]

 

Βρες το αθροισμα των 2 max που δεν ειναι στην ιδα θεση

 

Οκ αλλα με αυτο τι εννοουσες?

 

Δοκιμασα τον τροπο αλλα πχ για τον Β={4,1,1,1,1} δεν δουλευει ουτε για τον Γ={1,5,6,2,1}

[albNik]

Οκ αλλα με αυτο τι εννοουσες?

Οτι i<>j Να μην βρεις το A+A+i-i=2A.

Αλλα οι θεσεις μπορουν να αλλαζουν κυκλικά και μαλλον δεν  ειναι σωστος τροπος

 

 

Αυτο που ψαχνεις ειναι A+A[j] + max(i-j, n-i+j)  οπου n το μηκος του πινακα.

Οπος με τον προηγουμενο τροπο απλα έχεις και εναν τριτο πίνακα

βρισκεις το max

A+i

και του προσθετεις το max απο τα

A[j]-j

ή

A[j]+n-j

[defacer]

To i και j που λέμε έχουν πάντα διαφορά 1 (mod N) ή επιλέγονται ανεξάρτητα στο [0, N)?

[Anubis13]

το δεύτερο που λες defacer

 

έγραψα ενα πρόγραμμα το όποιο μάλλον δεν είναι γραμμικό

#include<stdio.h>

int max_distant_sum(int arr[], int K) {

    int dis = K-1;
    int i, j, max1, max2, dis2, res;
    while (dis >= 1){
        i = 0;
        j = dis;

        dis = j-i;
        dis2 = K-(j-i);
        max1 = arr[i] + arr[j] + dis;
        max2 = arr[i] + arr[j] + dis2;
        if (max1 > max2)
          res = max1; 
        else 
          res = max2;

        while (j <= K-1) {
            if (max1 < arr[i] + arr[j] + dis)
                max1 = arr[i] + arr[j] + dis;
            if (max2 < arr[i] + arr[j] + dis2)
                max2 = arr[i] + arr[j] + dis2;
            if (max1 > max2)
                res = max1; 
            else 
                res = max2;
            i++;
            j++; 
            printf("Max1 = %d and dis = %d \n", res, dis);
        }
        //printf("Max1 = %d and dis = %d \n", max1, dis);
        dis--;
    }
    return res;
    //return max1;
}

/* Driver program to test above function */
int main()
{
  int arr[] = {10, 1, 9, 9, 1, 10, 1, 1, 1};
  printf("%d \n", max_distant_sum(arr, 9));
  getchar();
  return 0;
}

Επεξ/σία 14 Απριλίου 2014 από Anubis13