Diferența maximă absolută a elementelor din matrice (Revizuirea codului, C#, Provocare De Programare, Limită De Timp Depășită)

utilizator1181942 a intrebat.

Încerc să rezolv o întrebare din secțiunea de matrice:

Se dă un array de N numere întregi, A1, , A2 ,…, AN. Se returnează valoarea maximă a lui f(i, j) pentru toate 1 ≤ i, j ≤ N. f(i, j) se definește ca fiind |A[i] – A[j]| + |i – j|, unde |x| reprezintă valoarea absolută a lui x.

De exemplu

A=[1, 3, -1]

f(1, 1) = f(2, 2) = f(3, 3) = 0
f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3
f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4
f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5

Deci, obținem 5.

Am rezolvat problema corect, însă soluția mea nu este cea optimizată. Iată soluția mea:

public int maxArr(List<int> A) {
    if (A==null || A.Count<=0) return 0;

    int sum = 0;
    int maxSum = 0;
    for (int i = 0; i<A.Count; i++)
    {
        for (int j= A.Count-1; j>i;j--)
        {
            sum = Math.Abs(A[i]-A[j]) + Math.Abs(i-j);
            if (sum > maxSum) maxSum = sum;
        }
    }

    return maxSum;
}

Înțeleg că, în cazul unor liste sau array-uri mai mari, buclele imbricate ar putea să nu fie o idee bună, dar ce pot face pentru a optimiza această soluție?

Actualizare: Am încercat, de asemenea, să elimin buclele imbricate

public int maxArr(List<int> A) {
    if (A==null || A.Count<=0) return 0;

    int sum = 0;
    int maxSum = 0;
    for (int k = 0; k<(A.Count)*(A.Count); k++)
    {
        int i = k/A.Count;
        int j = k%A.Count;

            sum = Math.Abs(A[i]-A[j]) + Math.Abs(i-j);
            if (sum > maxSum) maxSum = sum;

    }

    return maxSum;
}

În continuare acest lucru depășește limita de timp.

Comentarii

  • Mă întrebam doar, cât de rapid doriți să fie acest lucru și despre ce mărime de Listă vorbim? Chiar și atunci când verific o listă de 9000 de liste generate aleatoriu ints, soluția cu bucle imbricate durează doar 694 ms pentru a rula pe laptopul meu core i5. De asemenea, poate doriți să luați în considerare adăugarea etichetei [performance] și să reparați al doilea bloc de cod. De asemenea, v-aș recomanda să puneți promptul și exemplul de ieșire în blocuri de citate în loc de blocuri de cod.  > Por jrh.
  • @jrh vă mulțumesc pentru sugestiile de formatare. În legătură cu întrebarea dvs. despre cât de repede vreau să performeze codul, chiar nu știu, am crezut că a doua este soluția optimizată, dar rezolv întrebări pe interviewbit.com și spune că aceasta nu este soluția optimizată.-  > Por user1181942.
  • Știți dacă întrebarea de pe interviewbit se concentrează pe complexitatea algoritmică (de exemplu, O(1) vs. O(n) vs. O(n^2)) sau se concentrează pe timpul brut de procesare (de exemplu, trebuie să se termine în 500 ms)? Există cerințe spațiale (de exemplu, trebuie să ocupe doar X octeți de memorie RAM / nu poate aloca memorie suplimentară)?  > Por jrh.
  • De asemenea, există vreun motiv pentru care utilizați List în loc de o matrice reală (int[])?-  > Por jrh.
  • @jrh nu există cerințe spațiale. Cred că au în vedere complexitatea algoritmică. De asemenea, folosesc List pentru că scheletul metodei era deja dat și avea ca argument List.-  > Por user1181942.
2 răspunsuri
VisualMelon

Există o soluție (simplă) liniară în timp (și prin necesitate în spațiu). Mulțumirile mele pentru „persoana aleatoare de lângă mine” pentru că a fost o rață de cauciuc în acest proces.

Este într-adevăr foarte simplu: observați că |Ai - Aj| + |i - j| este doar maximul altor 4 funcții: + Ai + i - Aj - j, , + Ai - i - Aj + j, , - Ai + i + Aj - j, , - Ai - i + Aj + j.

Știind acest lucru, putem calcula o jumătate din fiecare dintre acestea (de ex. + Ai + i) pentru fiecare valoare în timp liniar și să le stocăm într-o matrice. Acum, partea pe jumătate inteligentă este următoarea: dacă ne „uităm” la punctul j, , știm că dacă cel mai bun partener al nostru (i) se află în stânga noastră (adică i <= j), atunci acesta este i la stânga noastră cu cel mai mare + Ai + i fie - Ai - i, , la care vom adăuga - Aj - j sau + Aj - j pentru a calcula rezultatul. Același lucru este valabil și pentru j din stânga noastră, (cu excepția celui actual j), și pentru j de lângă el, etc. Acest lucru înseamnă că putem calcula „cel mai bun is pentru js din dreapta lor, toate în același timp (liniar) și apoi doar să le căutăm atunci când le comparăm cu fiecare j. Același lucru se poate spune și pentru j < i.

În mod corespunzător, putem calcula 4 array-uri, câte unul pentru fiecare dintre cele 4 funcții pentru care trebuie să găsim maximul, dar care să conțină doar Ai și i și să înlocuim orice element mai mic decât orice element din dreapta (sau din stânga) cu cel mai mare element din dreapta (sau din stânga):

Cu aceste 4 tablouri construite (în timp liniar), putem face o buclă prin tablou, calculând cealaltă jumătate (de ex. - Aj - j) și să aflăm valoarea maximă a adunării fiecărei jumătăți cu cealaltă jumătate corespunzătoare. Soluția noastră este atunci doar maximul acestor sume.

În realitate, acest lucru poate fi implementat foarte simplu, ca o singură trecere peste matricea originală, unde ținem evidența celei mai mari sume. + Ai + i și - Ai + i, și le comparăm cu cele mai mari și cele mai mici. Aj și j (putem argumenta, din simetrie, că trecerea în sens invers este inutilă – știm că optimul are o „stânga” și o „dreapta”, trebuie să ne uităm doar la una dintre ele).

/// <summary>
/// Finds the max of |Ai - Aj| + |i - j|
/// </summary>
/// <param name="A">The array of Ai</param>
/// <returns>The max of |Ai - Aj| + |i - j|</returns>
public static int SimpleSuperiorMaxArr(int[] A)
{
    int best = 0; // known lower bound

    int bestPosi = 0;
    int bestNegi = 0;
    bool first = true;

    for (int i = 0; i < A.Length; i++)
    {
        int posi = A[i] - i;
        int negi = -A[i] - i;

        if (first || posi > bestPosi)
        {
            bestPosi = posi;
        }

        if (first || negi > bestNegi)
        {
            bestNegi = negi;
        }

        int posj = -A[i] + i;
        int negj = A[i] + i;

        int pos = bestPosi + posj;
        int neg = bestNegi + negj;

        int m = Math.Max(pos, neg);

        if (m > best)
        {
            best = m;
        }

        first = false;
    }

    return best;
}

datorită simplității algoritmului, îl putem implementa în Excel fără nici un fel de probleme!

Toate funcțiile sunt ca în stânga, iar rândurile „optime” sunt cele care reprezintă maximul dintre valoarea curentă și cea anterioară (sau doar curentă pentru prima coloană). Rețineți că funcționează de la stânga la dreapta, astfel încât „cele mai bune” rânduri nu scad niciodată în valoare spre dreapta. „ans” este doar valoarea maximă a tuturor rândurilor din perechea de rânduri de jos.

Edit: codul vechi păstrat pentru posteritate:

Acest cod nu este codul de cea mai bună calitate din toate timpurile, dar pare să funcționeze.

/// <summary>
/// Finds the max of |Ai - Aj| + |i - j|
/// </summary>
/// <param name="A">The array of Ai</param>
/// <returns>The max of |Ai - Aj| + |i - j|</returns>
public static int SuperiorMaxArr(int[] A)
{
    // Computes the array of Ai * ac + i * ic
    int[] ComputeInfoArray(int ac, int ic) // for our case, ic and direction are equal
    {
        int direction = -ic; // if we are adding i, then we are the 'right' array, otherwise we are 'left' array
        int[] iarr = new int[A.Length];

        bool first = true;
        int b = 0; // current best

        int s = direction > 0 ? 0 : A.Length - 1;
        int e = direction > 0 ? A.Length : -1;

        for (int i = s; i != e; i += direction)
        {
            int t = A[i] * ac + i * ic;

            if (first || t > b)
            {
                first = false;
                b = t;
            }

            iarr[i] = b;
        }

        return iarr;
    }

    int[] LeftLow = ComputeInfoArray(1, -1); // + Ai - i
    int[] LeftHigh = ComputeInfoArray(-1, -1); // - Ai - i
    int[] RightLow = ComputeInfoArray(1, 1); // + Ai + i
    int[] RightHigh = ComputeInfoArray(-1, 1); // - Ai + i

    int best = 0; // known lower bound

    for (int j = 0; j < A.Length; j++)
    {
        int ll = LeftLow[j] + j - A[j];
        int lh = LeftHigh[j] + j + A[j];
        int rl = RightLow[j] - j - A[j];
        int rh = RightHigh[j] - j + A[j];

        // in truth, we can just compute ll + lh

        int max = Math.Max(Math.Max(ll, lh), Math.Max(rl, rh));

        if (max > best)
            best = max;
    }

    return best;
}

Comentarii

  • Mulțumesc! Mulțumesc pentru explicația privind motivul pentru care putem ține cont doar de A[i] și i. Chiar și cu ajutorul indicațiilor din interviewbit, nu am reușit să înțeleg logica în mod corespunzător. Explicația ta a făcut-o mai clară.  > Por utilizator1181942.
paparazzo

Din moment ce j > i puteți sări peste un apel la Math.Abs

sum = Math.Abs(A[i]-A[j]) + j - i;

Comentarii

  • Aceasta chiar nu este o revizuire a codului, se pare că este o soluție alternativă parțială. Poți să abordezi ceva în cod pentru a o îmbunătăți?-  > Por pacmaninbw.
  • @pacmaninbw Dacă a sări peste un apel la Math.Abs nu este o revizuire de cod, atunci cum ai numi-o?-  > Por paparazzo.