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(lo{g}_{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.