Egy vektor, két feladat

Adott egy \(n\) elemű egész számokat tartalmazó \(A\) vektor.

1. Adjuk meg azt a \(P\) és \(Q\) indexet, ami maximalizálja a \(\sum_{i=P}^{Q}A[i]\) részvektort. Az algoritmus műveletideje legyen \(O(n)\).

2. Válasszuk ki a vektor második legkisebb elemét \(n + O(log_{2}n)\) összehasonlítással.

Frissítés 2019 október 7.

A második feladatot Lőry megoldotta, de sose jutottunk el az első megoldásáig. Most kigondoltam, aztán ellenőrzésképpen rá is keresetem a neten…

Olyan sok lehetőségünk nincs, tekintve, hogy csak egyszer mehetünk végig az input vektoron. Világos, hogy valami olyan invariánst kell kereseni, amit a következő elemre lépve fent tudunk tartani, és a végén a feladat megoldását adja.

Egy lehetséges ötlet az, hogy minden indexre próbáljuk meghatározni azt a legnagyobb részösszeget, ami az adott elemnél végződik.

Ciklusváltozónak válasszuk a kis \(q\)-t, és vezessük be a kis \(p\)-t is, a hozzátartozó intervallum kezdetét, az összeg legyen \(m\) és tartsuk még nyilván a \(M\) maximum összeget is, valamint az ehhez tartozó nagy \(P\), \(Q\) indexeket.

Induláskor legyen \(p = q = P = Q = 0\) és \(m = M = A[0]\).

Ha megvagyunk \(q\)-ig, akkor \(q + 1\)-re viszonylag könnyen átléphetünk, hiszen ha \(m\) negatív volt, akkor új intervallumot kell kezdenünk, ha pedig pozitív, akkor érdemes az előzőt folytatni.

Ezután már csak a \(P\), \(Q\) és \(M\) beállítgatása van hátra és kész is vagyunk:

function maxContiguousSum(A): 
  p = q = P = Q = 0
  m = M = A[0]
  for q in 1 .. A.length:
    if m < 0:
      (p, m) = (q, A[q])
    else:
      m = A[q] + m

    if m > M:
      (P, Q, M) = (p, q, m)
  return (P, Q)

Ez a feladat egyébként az irodalomban maxium subarray problem néven ismert, a fenti megoldás pedig a Kadane algoritmus egy változata.